From c68fe5a45bcad9cf3bb94bd192bdc2bbbe5a07d1 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Sat, 7 Aug 2021 15:13:50 -0400
Subject: Fixup query problem definitions

---
 mgr.tex | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

(limited to 'mgr.tex')

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
-- 
cgit v1.2.3

