From 4837657588edfc98ecb61cf5ba8f76655194b937 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 7 Oct 2021 13:09:42 +0200 Subject: Adjust wording --- mgr.tex | 19 +++++++++---------- 1 file changed, 9 insertions(+), 10 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index 9d9d0dc..a84c179 100644 --- a/mgr.tex +++ b/mgr.tex @@ -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} -- cgit v1.2.3