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)$:↵
↵
```cpp↵
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:↵
↵
1. **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.↵
↵
2. **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 > l$ and $a[m] > 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:↵
↵
```cpp↵
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 > 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 > i$ with $a[j] < 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:↵
↵
```cpp↵
/*↵
*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:↵
↵
```cpp↵
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)↵
↵
[Static Range Minimum Queries](https://cses.fi/problemset/task/1647)↵
↵
> 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.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
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) {↵
int v = l;↵
for (int k = 19; k >= 0; k--)↵
if (up[v][k] <= r) v = up[v][k];↵
return a[v];↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n, q;↵
cin >> n >> q;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++) cin >> a[i];↵
↵
mono_st<int, true> rmq(a);↵
↵
while (q--) {↵
int l, r;↵
cin >> l >> r;↵
cout << rmq.query(l - 1, r - 1) << "\n";↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## 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](https://codeforces.me/gym/104603/problem/A) 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 > 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 < E_i \leq X/2$, or $X/2 < E_i \leq X$ so $X \bmod E_i = X - E_i < 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 > 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$**:↵
↵
```cpp↵
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 $> X$ (they can't reduce $X$), and stop at the first one with value $\leq X$.↵
↵
Then the full query is:↵
↵
```cpp↵
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!
↵
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)$:↵
↵
```cpp↵
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:↵
↵
1. **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.↵
↵
2. **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 > l$ and $a[m] > 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:↵
↵
```cpp↵
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 > 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 > i$ with $a[j] < 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:↵
↵
```cpp↵
/*↵
*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:↵
↵
```cpp↵
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)↵
↵
[Static Range Minimum Queries](https://cses.fi/problemset/task/1647)↵
↵
> 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.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
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) {↵
int v = l;↵
for (int k = 19; k >= 0; k--)↵
if (up[v][k] <= r) v = up[v][k];↵
return a[v];↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n, q;↵
cin >> n >> q;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++) cin >> a[i];↵
↵
mono_st<int, true> rmq(a);↵
↵
while (q--) {↵
int l, r;↵
cin >> l >> r;↵
cout << rmq.query(l - 1, r - 1) << "\n";↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## 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](https://codeforces.me/gym/104603/problem/A) 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 > 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 < E_i \leq X/2$, or $X/2 < E_i \leq X$ so $X \bmod E_i = X - E_i < 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 > 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$**:↵
↵
```cpp↵
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 $> X$ (they can't reduce $X$), and stop at the first one with value $\leq X$.↵
↵
Then the full query is:↵
↵
```cpp↵
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!
