Hello everyone! In this blog I want to share a simple but elegant technique: answering RMQ (Range Minimum/Maximum Queries) using binary lifting on what I'm calling the Monotonic Stack Tree.
I came up with this technique independently and I'm not sure if it has an established name. If you've seen it before under a different name, I'd love to know! For now, I'll call it the Monotonic Stack Tree since the tree structure comes directly from the classic monotone stack.
The idea is not complicated, but I find it beautiful: the next-greater-element relationships naturally form a tree, and climbing that tree with binary lifting solves RMQ in $$$O(\log n)$$$ per query. No segment tree, no sparse table. Just a stack and a lifting table.
Prerequisites
You should be comfortable with:
- The classic stack-based algorithm for computing the Next Greater Element.
- Binary lifting.
Building the tree
Given an array $$$a[0], a[1], \ldots, a[n-1]$$$ of elements, define $$$\text{nge}(i)$$$ as the index of the first element to the right of $$$i$$$ that is strictly greater than $$$a[i]$$$. If no such element exists, set $$$\text{nge}(i) = n$$$ (a virtual root with value $$$+\infty$$$).
Now build a rooted tree: the parent of node $$$i$$$ is $$$\text{nge}(i)$$$. This is the Monotonic Stack Tree.
For example, consider $$$a = [2, 5, 1, 4, 3, 7, 6]$$$:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Value | 2 | 5 | 1 | 4 | 3 | 7 | 6 |
| Parent | 1 | 5 | 3 | 5 | 5 | $$$\infty$$$ | $$$\infty$$$ |
The parent of each node is the index of its next greater element. Nodes 5 and 6 have no greater element to their right, so their parent is the virtual root ($$$+\infty$$$).
The resulting tree looks like this:
We compute this with the classic monotone stack in $$$O(n)$$$:
vector<int> nge(n, n);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
nge[st.top()] = i;
st.pop();
}
st.push(i);
}
Two important properties of this tree:
The path from any node to the root is strictly increasing in value. This follows directly from the definition: each parent is strictly greater than its child.
The maximum of any range $$$[l, r]$$$ is an ancestor of $$$l$$$. This is the crucial insight that makes RMQ possible.
Why property 2 holds
Claim: For any range $$$[l, r]$$$, the position of the maximum element is an ancestor of $$$l$$$ in the Monotonic Stack Tree.
Proof: Let $$$m$$$ be the position of the maximum in $$$[l, r]$$$. We prove $$$m$$$ is an ancestor of $$$l$$$ by induction.
If $$$m = l$$$, we're done. Otherwise $$$m \gt l$$$ and $$$a[m] \gt a[l]$$$, so there exists a first element greater than $$$a[l]$$$ in the range $$$(l, r]$$$. That element is $$$\text{nge}(l)$$$, and by definition $$$\text{nge}(l) \leq m$$$, so $$$\text{nge}(l) \in [l+1, r]$$$.
Now the maximum of the subrange $$$[\text{nge}(l), r]$$$ is still $$$a[m]$$$ (since $$$m \geq \text{nge}(l)$$$). By induction, $$$m$$$ is an ancestor of $$$\text{nge}(l)$$$, which is the parent of $$$l$$$. So $$$m$$$ is an ancestor of $$$l$$$. $$$\blacksquare$$$
RMQ with binary lifting
Since the path from $$$l$$$ to the root is strictly increasing and $$$\max(a[l..r])$$$ is an ancestor of $$$l$$$, we just need to find the deepest ancestor of $$$l$$$ whose index is $$$\leq r$$$. That ancestor holds the maximum value.
We precompute the standard binary lifting table: $$$\text{up}[i][k]$$$ = the $$$2^k$$$-th ancestor of $$$i$$$ in the Monotonic Stack Tree. Then:
int rmq(int l, int r) {
int v = l;
for (int k = LOG - 1; k >= 0; k--) {
if (up[v][k] <= r) {
v = up[v][k];
}
}
return a[v];
}
We try jumps from largest to smallest. If jumping $$$2^k$$$ levels would land us at an index $$$\leq r$$$, we take the jump. At the end, $$$v$$$ is the deepest reachable ancestor within $$$[l, r]$$$, and $$$a[v]$$$ is the answer.
For example, to answer $$$\max(a[0..4])$$$: we start at index 0 (value 2) and walk up. Its parent is index 1 (value 5), which satisfies $$$1 \leq 4$$$, so we jump there. The next parent is index 5 (value 7), but $$$5 \gt 4$$$, so we stop. The answer is $$$a[1] = 5$$$.
Note: this is plain binary lifting on the Monotonic Stack Tree, we are not computing any LCA. We are simply walking up the ancestors of $$$l$$$ and stopping at the right one.
Complexity
- Preprocessing: $$$O(n)$$$ for the stack + $$$O(n \log n)$$$ for the lifting table = $$$O(n \log n)$$$.
- Per query: $$$O(\log n)$$$.
- Space: $$$O(n \log n)$$$.
Comparison with other approaches
| Approach | Build | Query | Space |
|---|---|---|---|
| Sparse Table | $$$O(n \log n)$$$ | $$$O(1)$$$ | $$$O(n \log n)$$$ |
| Segment Tree | $$$O(n)$$$ | $$$O(\log n)$$$ | $$$O(n)$$$ |
| Monotonic Stack Tree + Lifting | $$$O(n \log n)$$$ | $$$O(\log n)$$$ | $$$O(n \log n)$$$ |
On paper, the Monotonic Stack Tree doesn't beat sparse table or segment tree at their own game. So why care? Maybe because learning new stuff is fun :) And also because the tree structure opens up possibilities beyond plain RMQ. In the Alfajores application below, we'll see a problem where having the actual tree lets us do something that a sparse table or segment tree can't do as naturally.
Min vs max, and duplicates
Everything works symmetrically. If you build the tree using the Next Smaller Element instead (parent of $$$i$$$ is the first $$$j \gt i$$$ with $$$a[j] \lt a[i]$$$), the path from any node to the root is strictly decreasing, and you get Range Minimum Queries.
If the array can have duplicate values, use next greater or equal ($$$a[j] \geq a[i]$$$) when building the tree, with ties broken by index. The proof of property 2 goes through unchanged.
Implementation as a struct
Here is a compact, reusable struct in the style of a competitive programming library. It supports both min and max via a template parameter:
/*
*Description:* Static RMQ via Monotonic Stack Tree + binary lifting,
* build O(n log n), query O(log n), positions [0, n - 1]
*Status:* Tested on CSES Static Range Minimum Queries
*/
template<class T, bool isMin = true>
struct mono_st {
int n;
vector<T> a;
vector<array<int, 20>> up;
mono_st() {}
mono_st(vector<T> &v) : n(v.size()), a(v), up(n + 1) {
auto cmp = [&](int i, int j) {
return isMin ? a[j] < a[i] : a[j] > a[i];
};
vector<int> nge(n, n);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && cmp(st.top(), i)) {
nge[st.top()] = i;
st.pop();
}
st.push(i);
}
for (int i = 0; i < n; i++) up[i][0] = nge[i];
up[n][0] = n;
for (int k = 1; k < 20; k++)
for (int i = 0; i <= n; i++)
up[i][k] = up[up[i][k - 1]][k - 1];
}
T query(int l, int r) { // [l, r], 0-indexed
int v = l;
for (int k = 19; k >= 0; k--)
if (up[v][k] <= r) v = up[v][k];
return a[v];
}
};
Usage:
mono_st<int, true> rmq(a); // range minimum
mono_st<int, false> rmq(a); // range maximum
cout << rmq.query(l, r);
Practice problem: Static Range Minimum Queries (CSES)
Given an array of $$$n$$$ integers, process $$$q$$$ queries: what is the minimum value in range $$$[a, b]$$$?
$$$1 \leq n, q \leq 2 \cdot 10^5$$$, $$$\quad 1 \leq x_i \leq 10^9$$$, $$$\quad 1 \leq a \leq b \leq n$$$
This is a direct application. Build the Next Smaller Element tree and answer each query with binary lifting.
Application: Alfajores with range queries
Now let's see where the Monotonic Stack Tree structure truly shines: in problems where you need to walk along the relevant elements in a range, not just find an aggregate.
The original problem
Alfajores from 2023 Argentinian Programming Tournament (TAP).
Seba has $$$X$$$ alfajores and visits $$$M$$$ offices in order. The $$$i$$$-th office has $$$E_i$$$ employees. At each office, he distributes alfajores equally, so the remainder is $$$X \bmod E_i$$$, which becomes the new $$$X$$$ for the next office. Given $$$X$$$, compute $$$X \bmod E_1 \bmod E_2 \bmod \cdots \bmod E_M$$$.
The basic insight
Taking $$$X \bmod E_i$$$ only changes $$$X$$$ when $$$E_i \leq X$$$. If $$$E_i \gt X$$$, nothing happens. Furthermore, each time $$$X$$$ actually changes, it at least halves: if $$$E_i \leq X$$$, then either $$$E_i \leq X/2$$$ so $$$X \bmod E_i \lt E_i \leq X/2$$$, or $$$X/2 \lt E_i \leq X$$$ so $$$X \bmod E_i = X - E_i \lt X/2$$$. Either way, $$$X$$$ halves. So the number of effective reductions is $$$O(\log X)$$$.
Extending to range queries
Now suppose we have $$$Q$$$ queries, each of the form: given $$$X$$$, $$$l$$$, $$$r$$$, compute $$$X \bmod E_l \bmod E_{l+1} \bmod \cdots \bmod E_r$$$.
Build the Next Smaller on the array $$$E$$$: the parent of position $$$i$$$ is the first $$$j \gt i$$$ with $$$E_j \leq E_i$$$. Precompute binary lifting on this tree.
The path from any position $$$l$$$ to the root is the sequence of decreasing elements, exactly the elements that could reduce $$$X$$$. To answer a query $$$(X, l, r)$$$, we walk along this path using binary lifting, but instead of finding the minimum, we find the first ancestor of $$$l$$$ within $$$[l, r]$$$ with value $$$\leq X$$$:
int find_next(int pos, int r, long long X) {
if (E[pos] <= X) return pos;
int v = pos;
for (int k = LOG - 1; k >= 0; k--)
if (up[v][k] <= r && E[up[v][k]] > X)
v = up[v][k];
int p = up[v][0];
return (p <= r) ? p : -1;
}
The logic: we skip over ancestors with value $$$ \gt X$$$ (they can't reduce $$$X$$$), and stop at the first one with value $$$\leq X$$$.
Then the full query is:
long long solve(long long X, int l, int r) {
int pos = l;
while (pos <= r) {
int p = find_next(pos, r, X);
if (p == -1) break;
X %= E[p];
pos = up[p][0];
}
return X;
}
Each call to find_next is $$$O(\log M)$$$, and we call it at most $$$O(\log X)$$$ times (since $$$X$$$ halves each time). Total per query: $$$O(\log X \cdot \log M)$$$.
The crucial point: the path in the Monotonic Stack Tree from $$$l$$$ to the root is exactly the decreasing subsequence that matters for the modulo chain. Binary lifting lets us jump along this path efficiently, and the constraint $$$\leq r$$$ lets us restrict to any subrange.
Final thoughts
I should be honest: most problems where you'd use this technique can also be solved with a segment tree + walking (finding the first element satisfying some condition in a range). The complexity ends up being the same, and segment trees are more standard.
But I still think it's a beautiful idea. There's something satisfying about realizing that the monotone stack relationships form a tree, that paths in this tree are monotonic, and that this single observation is enough to answer RMQ. It connects two things that don't obviously belong together, and I like that.
If you know problems where this viewpoint leads to a nicer solution, or if this technique already has a name, I'd love to hear about it in the comments!
