diff options
| -rw-r--r-- | mgr.tex | 11 |
1 files changed, 10 insertions, 1 deletions
@@ -487,11 +487,20 @@ Now when given a query $x$, $y$, we: \begin{enumerate} \item Lookup $i := \indextable[y]$ and $j := \indextable[x] - 1$. \item Perform an RMQ query on $\prefixtable[i, j]$, giving us index $k$ of - the minimal value in that range. + the minimal value in that range. \label{hmd-algo-lookup} \item Lookup the corresponding vertex as $z := \posttable[k]$. This is the answer to our query. \end{enumerate} +We can detect the siutation of there not being a marked node between $x$ and $y$ +during step \ref{hmd-algo-lookup} by checking if $\prefixtable[k]$ is smaller +than the pre-order index of $y$. If it isn't, then all the nodes on the path +from $x$ to $y$ were unmarked (had higher values in the modified \prefixtable\ +since values at indices corresponding to unmarked nodes are set to $\infty$), +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). + \section{Solving branch infix regular queries} With the above problem solved, we are ready to finish our solution to the branch |