diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-07 15:13:50 -0400 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-07 15:13:50 -0400 |
commit | c68fe5a45bcad9cf3bb94bd192bdc2bbbe5a07d1 (patch) | |
tree | f27e5453e2163ae46c103f8d08f42f3c705db5ff | |
parent | 323c69fe6c953319f464bfc4d34c75876af57d88 (diff) |
Fixup query problem definitions
-rw-r--r-- | mgr.tex | 13 |
1 files changed, 7 insertions, 6 deletions
@@ -105,7 +105,7 @@ d \subsection{Least Common Ancestor} \queryproblem{% - Least Common Ancestor (LCA) + Least Common Ancestor (LCA) Queries }{% a tree $T$. }{% @@ -205,11 +205,12 @@ defines We can now reduce the problem to the following: -\queryproblem{Highest Marked Descendant on Path}{% - a tree $T$ with distinguished black vertices +\queryproblem{Highest Marked Descendant on Path Queries}{% + a tree $T$ with set $M \subseteq V(T)$ of marked vertices. }{% - given a vertex $x$, its descendant $y$, find the node $z$ that - is the highest black node on the path between $x$ and $y$ + given a vertex $x$, its descendant $y$, find the node $z \in M$ that + is the highest marked node on the path between $x$ and $y$, if such $z$ + exists. } We will build an index structure, constructible in linear time, that allows us @@ -220,7 +221,7 @@ Berkman and Vishkin for computing LCA queries. First, let's define an auxillary problem we will use, that of Range Minimum Queries (RMQ): -\queryproblem{Range Minimum Query}{% +\queryproblem{Range Minimum Queries}{% an array $A$ of integers. }{% given indices $i$ and $j$, return the index of the smallest |