m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-13 15:13:33 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-13 15:13:33 +0200
commit8063665da549dff9c3b3909c4151ecad146982fa (patch)
treee59024ce118bcc8788c61ed5bdc07bea7c52a6b9
parent32b338597d4877eae8578d5b6986953e447c0847 (diff)
Describe no marked vertex edge case
-rw-r--r--mgr.tex11
1 files changed, 10 insertions, 1 deletions
diff --git a/mgr.tex b/mgr.tex
index bf2f507..6c4fb1d 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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