m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex34
1 files changed, 28 insertions, 6 deletions
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