From 19d1b7e6dbdc2e15415b332668b4df856be77798 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Wed, 4 Aug 2021 01:24:27 +0200
Subject: Describe black-white algorithm

---
 mgr.tex | 51 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 49 insertions(+), 2 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index aaeecd3..4c50cce 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -134,10 +134,57 @@ is the highest black node on the path between $x$ and $y$.
 
 We will build an index structure, constructible in linear time, that allows us
 to handle such queries in constant time. The structure is heavily inspired by
-Bender and Farach-Colton's presentation of an algorithm originally attributed to
+Bender and Farach-Colton's presentation of an algorithm originally described by
 Berkman and Vishkin for computing LCA queries.
 
-\subsection{High level overview}
+First, let's define an auxillary problem we will use, that of Range Minimum
+Queries (RMQ):
+
+\emph{Given}: an array $A$ of integers.
+
+\emph{Queries}: given indices $i$ and $j$, return the index of the smallest
+element in the subarray $A[i, j]$.
+
+Fact: RMQ queries can be answered in constant time after linear preprocessing of
+the input array.
+
+We turn to describing the index structure for our tree problem.
+
+First, we create the array $POST$ of length $n$, which is the post-order of the
+nodes.
+
+Next, we label each node of the tree with its pre-order number. We create the
+array $PRE$ with the corresponding pre-order labels of the nodes in $POST$, i.e.
+if $POST[i] = v$, then $PRE[i]$ is $v$'s pre-order number.
+
+Finally, for each node of the tree, we record its index in $POST$ in the array
+$INDEX$.
+
+Observation: given a node $x$ and its descendant $y$, looking at the range
+$PRE[INDEX[y], INDEX[x] - 1]$, all the values in this range are descendants of
+$x$, and the values smaller than $PRE[INDEX[y]]$ correspond to ancestors of $y$.
+In particular, the minimum of that range corresponds to the highest ancestor of
+$y$ that's a descendant of $x$.
+
+In our problem, we only care about ancestors of $y$ that are colored black. So
+we perform one final modification of our data structure: for all non-black
+vertices $v$, we change $PRE[INDEX[v]]$ to $\infty$ (which can be represented by
+$n+1$, an integer greater than any node's pre-order label). With $PRE$ modified
+like this, we observe that now the minimum value of $PRE[INDEX[y], INDEX[x] -
+1]$ corresponds exactly to the answer of our queries -- the highest black node
+between $x$ and $y$.
+
+We preprocess $PRE$ for RMQ queries in linear time.
+
+Now when given a query $x$, $y$, we:
+
+\begin{enumerate}
+    \item Lookup $i := INDEX[y]$ and $j := INDEX[x] - 1$.
+    \item Perform an RMQ query on $PRE[i, j]$, giving us index $k$ of the
+        minimal value in that range.
+    \item Lookup the corresponding vertex as $z := POST[k]$. This is the
+        answer to our query.
+\end{enumerate}
 
 \section{Generalizing words to trees}
 
-- 
cgit v1.2.3