---
title: "Sparse Table and RMQ"
summary: O(1) range minimum queries on idempotent operations, with the log table that makes the proof two lines.
difficulty: core
tags: [RMQ, static, sparse table]
time: 1 per query
space: n log n
prereq: [structures/segment-tree]
see: [lca/rmq-lca, trees/euler-tour]
---

:::definition label="Sparse table"
$\operatorname{st}[j][i] = \min$ of the $2^j$ elements starting at $i$. Query $[l, r]$: take $k = \lfloor \log_2 (r - l + 1) \rfloor$ and answer $\min(\operatorname{st}[k][l], \operatorname{st}[k][r - 2^k + 1])$ — two overlapping blocks.
:::

```cpp sparse-table.cpp
vector<int> lg(n + 1);
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
int K = lg[n] + 1;
vector<vector<int>> st(K, vector<int>(n));
st[0] = a;
for (int j = 1; j < K; j++)
    for (int i = 0; i + (1 << j) <= n; i++)
        st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))]);
auto ask = [&](int l, int r) {                     // inclusive
    int k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
};
```

:::theorem title="Why overlap is allowed"
$\min$ is **idempotent** ($\min(x,x) = \min(x)$) and associative, so counting an element twice changes nothing; and $2^k \le r-l+1 < 2^{k+1}$ guarantees the two blocks cover the whole interval.
:::

:::props title="Which operations work, and which do not"
- **work**: `min`, `max`, `gcd`, bitwise `and`, bitwise `or` (all idempotent),
- **do not work**: `+` (double counting), `xor` (cancels!), parity of a count — for these use prefix sums or a segment tree,
- **count of minimum / "leftmost minimum"**: works with a custom combine that keeps `(value, tie-break)`; the idempotence requirement is on the *whole pair*, so store which side wins consistently.
:::

:::note title="Costs, honestly"
Build $O(n \log n)$ time and memory: at $n = 10^6$ that is $2 \times 10^7$ ints = 80 MB — plan for it or switch to a segment tree ($O(n)$ build, $O(\log n)$ query) or to the Cartesian-tree + Euler ±1-RMQ linear solution (@lca/rmq-lca) when $n$ is huge and queries are many.
:::

## Beyond min: three standard upgrades
:::example title="1. Static range sum, $O(1)$"
Prefix sums: $O(n)$ memory, $O(1)$ query — strictly better than a sparse table, because $+$ is invertible. The general rule: **invertible → prefix sums; idempotent → sparse table; neither → segment tree.**
:::

:::example title="2. Next greater element, in $O(1)$ after $O(n)$"
"First position to the right with value $> a[i]$" is not an aggregate over a set but a search. Precompute `nxt[i]` with a monotone stack ($O(n)$), then binary lift over `nxt` for "the $k$-th next greater", $O(\log n)$ per query. The stack handles the structure, lifting handles the repetition — a pattern that recurs in @directed/functional and @lca/binary-lifting.
:::

:::example title="3. Sparse table over a monoid, for 'is this range periodic'"
$\operatorname{st}[j][i]$ with combine = "hash of the concatenation" and *non*-overlapping queries gives you substring hashes at fixed length $2^j$ in $O(1)$ — the standard building block for LCP queries and "count distinct rotations" problems.
:::

:::problems
- [[CSES 1647]] Static Range Minimum Queries | https://cses.fi/problemset/task/1647 | easy | direct application
- [[CSES 1137]] Subtree Queries | https://cses.fi/problemset/task/1137 | core | Euler order + static vs dynamic contrast
:::