## 7 A Repetition-Aware CST
### Computing NSV, PSV, and RMQ  
To answer \(\textit{NSV}(i)\), we first look for the rule \(C[j]\) that contains \(\textit{LCP}[i+1]\): We binary search _Pos_ for the largest \(j^{\prime}\) such that \(\textit{Pos}[j^{\prime}]\leq i+1\) and then sequentially advance on \(C[cj^{\prime}..j]\) until finding the largest \(j\) such that \(pos=\textit{Pos}[j]+\sum_{cj^{\prime}\leq k<j}cover_{C[k]}\leq i+1\). At the same time, we compute \(\ell=\textit{Val}[j^{\prime}]+\sum_{cj^{\prime}\leq k<j}sum_{C[k]}\). Now, if \(\ell+min_{C[j]}<\textit{LCP}[i]\), it is possible that \(\textit{NSV}(i)\) is within the same \(C[j]\). In this case, we search recursively the tree expansion with root \(C[j]\) for the leftmost value to the right of \(i\) and smaller than \(\textit{LCP}[i]\): Let \(C[j]\to ab\) in the grammar. We recursively visit child \(a\) if \(\ell+min_{a}<\textit{LCP}[i]\) and \(pos+cover_{a}\geq i+1\). If we find no answer there, or we had decided not to visit \(a\), then we set \(\ell=\ell+sum_{a}\) and \(pos=pos+cover_{a}\) and recursively visit child \(b\) if \(\ell+min_{b}<\textit{LCP}[i]\). Note that if \(pos\geq i+1\) we do not need to enter \(b\), but can simply use the value \(min_{b}\) and the position \(pos+lmin_{b}\) for the minimum. If we also find no answer inside \(b\), or we had decided not to visit \(b\), we return with no value. On the other hand, if we reach a leaf \(l\) during the recursion, we sequentially scan the array \(\textit{LCP}[pos,pos+cover_{l}-1]\), updating \(\ell=\ell+\textit{LCP}[k]\) and increasing \(pos\). If at some position we find a value smaller than \(\textit{LCP}[i]\), we report the position \(pos\). If we return with no value from the first recursive call at \(C[j]\), it was because the only values smaller than \(\textit{LCP}[i]\) were to the left of \(i\). In this case, or if we had decided not to enter into \(C[j]\) because \(\ell+min_{C[j]}\geq\textit{LCP}[i]\), we sequentially scan \(C[j+1,n]\), while updating \(\ell=\ell+sum_{C[k]}\) and \(pos=pos+cover_{C[k]}\), until finding the first \(k\) such that \(\ell+min_{C[k]}<\textit{LCP}[i]\). Once we find such \(k\), we are sure that the answer is inside \(C[k]\). Thus we enter into \(C[k]\) with a procedure very similar to the one for \(C[j]\) (albeit slightly simpler as we know that all the positions are larger than \(i\)). In this case, as the LCP values are discrete, we know that if \(\ell+min_{C[k]}=\textit{LCP}[i]-1\), there is no smaller value to the left of the \(min\) value, so in this case we directly answer the corresponding \(lmin\) value, without accessing the _LCP_ array. The solution to \(\textit{PSV}(i)\) is symmetric. To answer \(\textit{RMQ}(x,y)\), we find the rules \(C[i]\) and \(C[j]\) containing \(x\) and \(y\), respectively. We sequentially scan \(C[i+1,j-1]\) and store the smallest \(\ell+min_{C[k]}\) value found (in case of ties, the leftmost). If the minimum is smaller than the corresponding values \(\ell+min_{C[i]}\) and \(\ell+min_{C[j]}\), we directly return the value \(pos+lmin_{C[k]}\) corresponding to position \(C[k]\). Else, if the global minimum in \(C[i]\) is equal to or less than the minimum for \(i<k<j\), we must examine \(C[i]\) to find the smallest value to the right of \(x-1\). Assume \(C[i]\to ab\). We recursively enter into \(a\) if \(pos+cover_{a}\geq x\), otherwise we skip it. Then, we update \(\ell=\ell+sum_{a}\) and \(pos=pos+cover_{a}\), and enter into \(b\) if \(pos<x\), otherwise we directly consider \(\ell+min_{b}\) as a candidate for the minimum sought. Finally, if we arrive at a leaf we scan it, updating \(\ell\) and \(pos\), and consider all the values \(\ell\) where \(pos\geq x\) as candidates to the minimum. The minimum for \(C[i]\) is the smallest among all candidates to minimum considered, and with \(pos+lmin_{b}\) or the leaf scanning process we know its global position. This new minimum is comparedwith the minimum of \(C[k]\) for \(i<k<j\).