diff options
| -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 |