diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 19 |
1 files changed, 9 insertions, 10 deletions
@@ -220,10 +220,10 @@ serve as examples and because we will be using them in our algorithm. algorithm for LCA. \textcite{schieber1988} used a similar approach but simplified the indexing structure, keeping the same time complexities. \textcite{berkman1993} showed a completely new approach to the problem, which -relies on answering range minimum queries (see below) about an array of properly -ordered tree vertices. \textcite{bender2000} offer a simpler presentation of the -algorithm in \cite{berkman1993} and note the equivalence between the LCA and RMQ -problems. +relies on answering range minimum queries (see below) about an array of the +tree's vertices arranged in a specific order. \textcite{bender2000} offer a +simpler presentation of the algorithm in \cite{berkman1993} and note the +equivalence between the LCA and RMQ problems. \subsection{Range Minimum Query (RMQ)} @@ -234,17 +234,16 @@ problems. element in the subarray $A[i, j]$. } -As mentioned above, \textcite{bender2000} show an \qpoptimal{} -algorithm for the RMQ problem. +\textcite{bender2000} show an \qpoptimal{} algorithm for the RMQ problem. Their method is as follows. First they show that a special case of the RMQ problem, $\pm1$ RMQ, can be solved in \qpoptimal. This restriction of the problem is enough to handle LCA queries. Then, for the general RMQ case, a Cartesian -tree\footnote{A Cartesian tree of a list is a binary tree with the list's +tree\footnote{A Cartesian tree of an array is a binary tree with the array's minimum element in its root, the root's children being Cartesian trees of the -left and right sublists around the minimal element. It can be constructed in -linear time.} of the list is built, and LCA queries on this tree correspond to -range minimum queries on the list. +left and right subarrays around the minimal element. It can be constructed in +linear time.} of the array is built, and LCA queries on this tree correspond to +range minimum queries on the array. \subsection{Word infix regular queries}\label{wordinfix} |