m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-07 13:09:42 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-07 13:09:42 +0200
commit4837657588edfc98ecb61cf5ba8f76655194b937 (patch)
tree35c99859f5fd15a84f7bcaac87673cd231f342c3
parentd772de735c8ac9ac73972c9c775be73a7818f025 (diff)
Adjust wording
-rw-r--r--mgr.tex19
1 files changed, 9 insertions, 10 deletions
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}