m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-07 14:32:32 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-07 14:32:32 +0200
commitf86a525bbe35b5602e3ddda9092447fe5771b670 (patch)
tree39abd93d91caa49be4dc0efe146d9ba6f4e81ac5
parent211b76591f2a35aa4234a7b1554abac8c4d10a0c (diff)
Reword things
-rw-r--r--mgr.tex15
1 files changed, 5 insertions, 10 deletions
diff --git a/mgr.tex b/mgr.tex
index 7074ec3..7e45d2f 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -378,9 +378,9 @@ The query problem we will solve is:
}
We begin with a similar construction as in the word case, i.e. we replace each
-vertex of the tree with a copy of the states of $A$. Call the set of $T$'s
-vertices, $V$, then our new graph has vertex set $V \times Q$, and we can refer
-to a specific vertex as $x.q$ for $x \in V$, $q \in Q$.
+vertex of the tree with a copy of the states of $A$. Our new graph has vertex
+set $V(T) \times Q$, and we can refer to a specific vertex as $x.q$ for $x \in
+V(T)$, $q \in Q$.
Again, each letter $a \in \Sigma$ defines a function $a : Q \to Q$, and these
functions induce edges in our ``fattened'' tree: consider a vertex $x$ of $T$,
@@ -415,7 +415,7 @@ subproblem.
\section{Highest Marked Descendant on Path}
-We can now reduce the problem to the following:
+We will show that the branch infix problem reduces to the following:
\queryproblem{Highest Marked Descendant on Path Queries}{%
a tree $T$ with set $M \subseteq V(T)$ of marked vertices.
@@ -430,11 +430,6 @@ to handle such queries in constant time. The structure is heavily inspired by
\textcite{bender2000}, where a simple algorithm for computing LCA queries is
presented.
-Recall that 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 \posttable\ of length $n$, which is the post-order of
the nodes.
@@ -447,7 +442,7 @@ Finally, for each node of the tree, we record its index in \posttable\ in the
array \indextable.
\begin{observation}
- given a node $x$ and its descendant $y$, looking at the range
+ 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