Sparse Table
O(1) query, O(n log n) buildConstant-time range queries for idempotent operations (min, max, gcd) on a static array. No updates. When the array never changes, this beats a segment tree on both speed and code size.
// use it on
CSES: Static Range Minimum Queries ↗
Range minimums on a fixed array, exactly what the table answers in O(1) each.
// the code
struct SparseTable { // min; works for any idempotent op
vector<vector<long long>> t;
SparseTable(const vector<long long>& a) {
int n = a.size(), K = __lg(n) + 1;
t.assign(K, a);
for (int j = 1; j < K; j++)
for (int i = 0; i + (1 << j) <= n; i++)
t[j][i] = min(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
}
long long query(int l, int r) { // min on [l, r]
int j = __lg(r - l + 1);
return min(t[j][l], t[j][r - (1 << j) + 1]);
}
};// more range queries