Describe no marked vertex edge case

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