diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 15 |
1 files changed, 5 insertions, 10 deletions
@@ -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 |