Solve RMQ (Range Minimum Query) by finding LCA (Lowest Common Ancestor)¶
Given an array A[0..N-1].
For each query of the form [L, R] we want to find the minimum in the array A starting from position L and ending with position R.
We will assume that the array A doesn't change in the process, i.e. this article describes a solution to the static RMQ problem
Here is a description of an asymptotically optimal solution. It stands apart from other solutions for the RMQ problem, since it is very different from them: it reduces the RMQ problem to the LCA problem, and then uses the Farach-Colton and Bender algorithm, which reduces the LCA problem back to a specialized RMQ problem and solves that.
Algorithm¶
We construct a Cartesian tree from the array A.
A Cartesian tree of an array A is a binary tree with the min-heap property (the value of parent node has to be smaller or equal than the value of its children) such that the in-order traversal of the tree visits the nodes in the same order as they are in the array A.
In other words, a Cartesian tree is a recursive data structure.
The array A will be partitioned into 3 parts: the prefix of the array up to the minimum, the minimum, and the remaining suffix.
The root of the tree will be a node corresponding to the minimum element of the array A, the left subtree will be the Cartesian tree of the prefix, and the right subtree will be a Cartesian tree of the suffix.
In the following image you can see one array of length 10 and the corresponding Cartesian tree.
The range minimum query [l, r] is equivalent to the lowest common ancestor query [l', r'], where l' is the node corresponding to the element A[l] and r' the node corresponding to the element A[r].
Indeed the node corresponding to the smallest element in the range has to be an ancestor of all nodes in the range, therefor also from l' and r'.
This automatically follows from the min-heap property.
And is also has to be the lowest ancestor, because otherwise l' and r' would be both in the left or in the right subtree, which generates a contradiction since in such a case the minimum wouldn't even be in the range.
In the following image you can see the LCA queries for the RMQ queries [1, 3] and [5, 9].
In the first query the LCA of the nodes A[1] and A[3] is the node corresponding to A[2] which has the value 2, and in the second query the LCA of A[5] and A[9] is the node corresponding to A[8] which has the value 3.
Such a tree can be built in $O(N)$ time and the Farach-Colton and Benders algorithm can preprocess the tree in $O(N)$ and find the LCA in $O(1)$.
Construction of a Cartesian tree¶
We will build the Cartesian tree by adding the elements one after another.
In each step we maintain a valid Cartesian tree of all the processed elements.
It is easy to see, that adding an element s[i] can only change the nodes in the most right path - starting at the root and repeatedly taking the right child - of the tree.
The subtree of the node with the smallest, but greater or equal than s[i], value becomes the left subtree of s[i], and the tree with root s[i] will become the new right subtree of the node with the biggest, but smaller than s[i] value.
This can be implemented by using a stack to store the indices of the most right nodes.
vector<int> parent(n, -1);
stack<int> s;
for (int i = 0; i < n; i++) {
int last = -1;
while (!s.empty() && A[s.top()] >= A[i]) {
last = s.top();
s.pop();
}
if (!s.empty())
parent[i] = s.top();
if (last >= 0)
parent[last] = i;
s.push(i);
}