From 8063665da549dff9c3b3909c4151ecad146982fa Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Wed, 13 Oct 2021 15:13:33 +0200 Subject: Describe no marked vertex edge case --- mgr.tex | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) (limited to 'mgr.tex') 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 -- cgit v1.2.3