From 32b338597d4877eae8578d5b6986953e447c0847 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Wed, 13 Oct 2021 15:12:19 +0200
Subject: Prove observation

---
 mgr.tex | 34 ++++++++++++++++++++++++++++------
 1 file changed, 28 insertions(+), 6 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index 7e45d2f..bf2f507 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -443,14 +443,36 @@ array \indextable.
 
 \begin{observation}
     Given a node $x$ and its descendant $y$, looking at the range
-    $\prefixtable[\indextable[y], \indextable[x] - 1]$, all the values in this
-    range are descendants of $x$, and the values smaller than
-    $\prefixtable[\indextable[y]]$ correspond to ancestors of $y$.  In
-    particular, the minimum of that range corresponds to the highest ancestor of
-    $y$ that is also a descendant of $x$.
+    $\prefixtable[\indextable[y], \indextable[x] - 1]$:
+    \begin{enumerate}
+        \item All the values in this range correspond to descendants of $x$.
+            \label{obs-descendants}
+        \item The values smaller than $\prefixtable[\indextable[y]]$ correspond
+            to ancestors of $y$. \label{obs-ancestors}
+        \item In particular, the minimum of this range corresponds to the
+            highest ancestor of $y$ that is also a descendant of $x$.
+            \label{obs-conclusion}
+    \end{enumerate}
 \end{observation}
 
-In our problem, we only care about ancestors of $y$ that are colored black. So
+The pre-order labels in \prefixtable\ are ordered according to a post-order. In
+a post-order, the root of a subtree is visited directly after all its
+descendants. Since $y$ is a descendant of $x$, all values between its position
+in \prefixtable\ and $x$'s position there will also be descendants of $x$,
+giving item \ref{obs-descendants}.
+
+The values in \prefixtable\ are pre-order numbers. In a pre-order, for a given
+node $z$, the only nodes that will have lower pre-order numbers are $z$'s
+ancestors, and the children of these ancestors that are to the left of the child
+towards $z$. By starting our range at index $\indextable[y]$, we've skipped over
+all of the second types of vertices with lower pre-order numbers, leaving only
+$y$'s ancestors as nodes in the range with a lower pre-order number. This gives
+us item \ref{obs-ancestors}.
+
+Items \ref{obs-descendants} and \ref{obs-ancestors} together give us item
+\ref{obs-conclusion}.
+
+In our problem, we only care about ancestors of $y$ that are marked. So
 we perform one final modification of our data structure: for all non-black
 vertices $v$, we change $\prefixtable[\indextable[v]]$ to $\infty$ (which can be
 represented by $n+1$, an integer greater than any node's pre-order label). With
-- 
cgit v1.2.3