diff options
Diffstat (limited to 'mgr.tex')
-rw-r--r-- | mgr.tex | 22 |
1 files changed, 21 insertions, 1 deletions
@@ -668,6 +668,24 @@ and $k$ will correspond to a marked node that's not on the path from $x$ to $y$ (or some unmarked vertex if there were no marked vertices at all in the range we check). +\begin{figure} + \centering + \def\svgwidth{0.5\columnwidth} + \input{tree-marked.pdf_tex} + \caption{ + A preprocessed marked tree. The marked vertices are colored dark grey. + To the left of each vertex is its pre-order number. To the right is its + post-order number. On the bottom is the table $\prefixtable$ with only + the marked vertices' prefix numbers not replaced by $\infty$. The red + rectangle marks the range for which we issue an RMQ question when + answering a highest marked descendant question form the vertex with + post-order index 7 down to the one with post-order index 2. + }\label{marked-figure} +\end{figure} + +See Figure \ref{marked-figure} for a visual example of the data structure +described. + \section{Answering branch infix regular questions} With the above problem solved, we are ready to finish our algorithm for branch @@ -685,7 +703,9 @@ copy of $Q$ on the path towards the copy of $Q$ that contains $y$?''. To achieve this, we create a copy of $T$ in which we mark the vertices where an edge from a $c$-colored vertex points to a vertex with a lower color. This tree we preprocess for highest marked descendant on path questions, solved in the -previous section. +previous section. Note that Figure \ref{marked-figure} is exactly the marked +tree we create and preprocess for the green color of the colored graph in Figure +\ref{tree-figure}. Now question answering can proceed similar to the word case. Given a question ``does the word on vertices from $x$ down to $y$ belong to $L$?'', let $x'$ be |