m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-07 15:13:50 -0400
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-07 15:13:50 -0400
commitc68fe5a45bcad9cf3bb94bd192bdc2bbbe5a07d1 (patch)
treef27e5453e2163ae46c103f8d08f42f3c705db5ff
parent323c69fe6c953319f464bfc4d34c75876af57d88 (diff)
Fixup query problem definitions
-rw-r--r--mgr.tex13
1 files changed, 7 insertions, 6 deletions
diff --git a/mgr.tex b/mgr.tex
index 9abfe49..f9ca98f 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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