Sparse table
Range minimum on a static array in , after preprocessing.
When
The array does not change and there are very many queries, or the query sits inside another loop (e.g. inside a binary search), so the of a segment tree matters.
The idea
. Level is built from level out of two halves: .
For a query of length , take . The two blocks of length , one from the start and one from the end, cover the whole range. They overlap, but that does not matter for the minimum:
The same holds for every operation with : maximum, gcd, and, or. Not for sums, where the overlap is counted twice.
Pitfalls
- Compute the logarithms once into an array (
lg[i] = lg[i / 2] + 1), not withlog2on doubles inside the query. - Memory is : for that is about values, 29 MB as
long long. With a 256 MB limit you are fine; with 64 MB, be careful.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Sparse table for range minimum on a static array.
// Build O(n log n), query O(1): [l, r] is covered by two overlapping blocks of length 2^k.
// Works for any idempotent operation (min, max, gcd), not for sums.
struct SparseTable {
vector<vector<ll>> st;
vector<int> lg;
SparseTable(const vector<ll>& a) {
int n = a.size();
lg.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
int levels = lg[max(n, 1)] + 1;
st.assign(levels, vector<ll>(n));
for (int i = 0; i < n; i++) {
st[0][i] = a[i];
}
for (int k = 1; k < levels; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
}
}
ll query(int l, int r) {
int k = lg[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
};
Tested on 1,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Static Range Minimum Queries · Range Queries