m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-11 13:44:39 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-11 13:45:01 +0100
commit0fe30fc2bafc5cb7c04806b29bb84634daba451d (patch)
tree13191a3746e54dcd134c7f6eb8b3a5ef58f2ab88
parent09eb93e92a4e6ebc832dee93d462429f57208941 (diff)
Clarify order
-rw-r--r--mgr.tex16
1 files changed, 8 insertions, 8 deletions
diff --git a/mgr.tex b/mgr.tex
index a9d75cb..fe6aaec 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -909,14 +909,14 @@ is the LCA closure of $W$.
Let's define $u_i := LCA(v_i, v_{i+1})$. By Observation
\ref{lca-observation}, each $u_i$ falls between $v_i$ and $v_{i+1}$ in the infix
-order, i.e. $W'$ sorted is the sequence $v_1, u_1, v_2, u_2, \ldots, u_{m - 1},
-v_m$ (note that in the way this sequence is written, some vertices might be
-repeated, e.g. it might be the case that $LCA(v_2, v_3) = v_2$, in which case
-$u_2$ will be equal to $v_2$). We claim that for every pair of vertices in $W'$,
-their LCA is also in $W'$. We'll proceed by induction, and it will be easier if
-we now rename the sorted $W'$ to $w_1 := v_1, w_2 := u_2, \ldots, w_{2m-2} :=
-u_{m-1}, w_{2m - 1} := v_m$. As quick recap, the following are properties of the
-sequence of $w_i$'s:
+order, i.e. $W'$ sorted by infix numbers is the sequence $v_1, u_1, v_2, u_2,
+\ldots, u_{m - 1}, v_m$ (note that in the way this sequence is written, some
+vertices might be repeated, e.g. it might be the case that $LCA(v_2, v_3) =
+v_2$, in which case $u_2$ will be equal to $v_2$). We claim that for every pair
+of vertices in $W'$, their LCA is also in $W'$. We'll proceed by induction, and
+it will be easier if we now rename the sorted $W'$ to $w_1 := v_1, w_2 := u_2,
+\ldots, w_{2m-2} := u_{m-1}, w_{2m - 1} := v_m$. As quick recap, the following
+are properties of the sequence of $w_i$'s:
\begin{enumerate}
\item For $i < j$, $\infixtable[w_i] \leq \infixtable[w_j]$.