i. Sparse Table

$O(1)$ queries on a static array after $O(n\log n)$ preprocessing. The plain table needs an idempotent operation ($x\circ x=x$: min, max, gcd, AND, OR), because the two query blocks overlap. The disjoint variant handles any associative operation in $O(1)$.

Sparse table

$s{p}_k[i]$ aggregates $[i,i+2^k)$, and a query $[l,r)$ takes two overlapping blocks of length $2^{\lfloor {\log }_2(r-l)\rfloor }$.

template<class T, class F> struct SparseTable {
    vector<vector<T>> sp; F f;
    SparseTable(const vector<T>& a, F f) : f(f) {
        int n = sz(a), K = __lg(max(n, 1)) + 1;
        sp.assign(K, a);
        for (int k = 1; k < K; k++)
            for (int i = 0; i + (1 << k) <= n; i++) sp[k][i] = f(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
    }
    T query(int l, int r) const {                  // [l, r), l < r
        int k = __lg(r - l);
        return f(sp[k][l], sp[k][r - (1 << k)]);
    }
};
// SparseTable st(a, [](int x, int y) { return min(x, y); });

Layout sp[k][i] (level-major) keeps each level contiguous, so the build is cache-friendly. For $n=10^6$ with 20 levels of int, that’s 80 MB; drop unneeded levels or switch to the $O(n)$ RMQ below.

Uses: LCA via Euler tour + RMQ; LCP of two suffixes via RMQ on the LCP array; range gcd; static range min inside binary search or two-pointer loops; “first position to the right with value $<x$” by binary lifting on the table ($O(\log n)$ descent over levels).

Proof: the overlapping-block query is correct for idempotent $f$

$s{p}_k[i]=f(a_i,a_{i+1},\dots ,a_{i+2^k-1})$ by induction: the build line combines two length-$2^{k-1}$ blocks covering exactly that range. For a query $[l,r)$ with $k=\lfloor {\log }_2(r-l)\rfloor$, both blocks $[l,l+2^k)$ and $[r-2^k,r)$ lie inside $[l,r)$ (since $2^k\le r-l$) and together cover all of $[l,r)$ (since $2^{k+1}>r-l$ forces $r-2^k<l+2^k$, so the two blocks overlap rather than leaving a gap). Every element of $[l,r)$ appears in at least one block, and elements in the overlap $[r-2^k,l+2^k)$ appear in both. Idempotence ($x\circ x=x$) means repeating an element in the fold doesn’t change the result — formally, $f$ idempotent and commutative/associative on a multiset extends to “folding any covering multiset containing every element at least once gives the same answer as folding the set”, since duplicate elements collapse. So $f(s{p}_k[l],s{p}_k[r-2^k])$, which folds the two (possibly overlapping) blocks, equals the fold over $[l,r)$ exactly. $■$

Disjoint sparse table

At level $k$, cut the array into blocks of length $2^{k+1}$; inside each block store suffix aggregates leftwards from the middle and prefix aggregates rightwards from it. For $l<r$ (inclusive), the level is the highest bit where $l$ and $r$ differ: they’re in the same block on opposite sides of its middle.

template<class T, class F> struct DisjointSparseTable {
    vector<vector<T>> t; vector<T> a; F f;
    DisjointSparseTable(const vector<T>& a_, F f) : a(a_), f(f) {
        int n = sz(a), K = max(1, __lg(max(n - 1, 1)) + 1);
        t.assign(K, vector<T>(n));
        for (int k = 0; k < K; k++) {
            int half = 1 << k;
            for (int mid = half; mid < n + half; mid += 2 * half) {
                if (mid - 1 < n) {
                    t[k][mid - 1] = a[mid - 1];
                    for (int i = mid - 2; i >= mid - half; i--) t[k][i] = f(a[i], t[k][i + 1]);
                }
                if (mid < n) {
                    t[k][mid] = a[mid];
                    for (int i = mid + 1; i < min(n, mid + half); i++) t[k][i] = f(t[k][i - 1], a[i]);
                }
            }
        }
    }
    T query(int l, int r) const {                  // inclusive [l, r]
        if (l == r) return a[l];
        int k = __lg(l ^ r);
        return f(t[k][l], t[k][r]);
    }
};

Proof: disjoint sparse table query correctness

Let $k=\lfloor {\log }_2(l\oplus r)\rfloor$, the index of the highest bit where $l$ and $r$ differ ($l<r$ so $l\oplus r>0$). Bits above $k$ agree between $l$ and $r$; write that shared high part as $B$ (a multiple of $2^{k+1}$ after shifting). Since bit $k$ differs and is the highest differing bit, $l$ has bit $k$ equal to $0$ and $r$ has it equal to $1$ (as $l<r$), so $l\in [B,B+2^k)$ and $r\in [B+2^k,B+2^{k+1})$ — i.e. both lie in the same length-$2^{k+1}$ block used at level $k$, with $l$ strictly left of that block’s midpoint $B+2^k$ and $r$ at or right of it. By construction, $t[k][l]$ is the suffix-aggregate from $l$ up to the midpoint, and $t[k][r]$ is the prefix-aggregate from the midpoint up to $r$, so $f(t[k][l],t[k][r])$ folds exactly $a_l,\dots ,a_r$ with no gap and no overlap (the two aggregates meet exactly at the midpoint, each element counted once). $■$

Tested against a brute-force fold over random associative non-idempotent operations (e.g. sum, matrix product) and random $[l,r]$, confirming it handles non-idempotent ops where the plain overlapping sparse table would double-count.

Uses: range products modulo a composite, range matrix products, range “max subarray sum” nodes, and huge numbers of queries ($10^7$) where a segment tree’s $\log$ would dominate. The same “prefix and suffix from the middle” idea is the offline divide and conquer for range DP queries (Divide and Conquer).

2D sparse table

$t_{a,b}[i][j]$ covers the rectangle $[i,i+2^a)\times [j,j+2^b)$. A query uses four overlapping rectangles, so it needs idempotence. Build and memory are $O(nm\log n\log m)$: a $500\times 500$ grid of int already needs about 80 MB. Alternatives: a 2D sliding window max with deques for fixed-size windows, per-row sparse tables with $O(\text{rows})$ queries, or a 2D segment tree.

Choosing a static structure

Operation	Structure	Query
sum, XOR (invertible)	prefix sums	$O(1)$
min, max, gcd, AND, OR	sparse table, or $O(n)$ RMQ (Farach-Colton-Bender, see RMQ)	$O(1)$
any associative	disjoint sparse table, sqrt tree	$O(1)$
associative, low memory	segment tree	$O(\log n)$
$k$-th smallest, counts by value	wavelet matrix, persistent segment tree	$O(\log n)$

Choosing a range-query structure in general

The full (update, query) matrix — the decision this whole chapter answers:

Updates	Queries	Structure	Cost
none	range query, idempotent op	sparse table / disjoint sparse table / sqrt tree	$O(1)$
none	range query, non-idempotent (sum)	prefix sums	$O(1)$
point	range query	Fenwick tree (sum-like) or segment tree (any monoid)	$O(\log n)$
range add	point query	Fenwick/segment tree over the difference array	$O(\log n)$
range add	range sum	two Fenwick trees, or a lazy segment tree	$O(\log n)$
range assign/add	range sum/min/max	lazy segment tree (Lazy Propagation)	$O(\log n)$
range chmin/chmax (+ range add)	range sum	segment tree beats (Segment Tree Beats)	amortized $O({\log }^{2}n)$
add a line/segment	min/max of lines at a point	Li Chao tree (Li Chao Tree)	$O(\log C)$
none, but queries are offline and “about value”, not position	$k$-th smallest, counts by value in a range	persistent segment tree / wavelet tree (Range Order Statistics)	$O(\log n)$
point, need every historical version	query any past version	persistent segment tree (Dynamic and Persistent Segment Trees)	$O(\log n)$, $O(\log n)$ new nodes
offline, hard to decompose (distinct counts, complex aggregates)	arbitrary range, reorderable	Mo’s algorithm (Mo’s Algorithm)	$O((n+q)\sqrt{n})$
offline, mixed update/query types	—	sqrt decomposition on queries, or CDQ divide and conquer (CDQ)	problem-dependent, usually $O((n+q)\sqrt{n})$ or $O(n{\log }^{2}n)$
point, values bounded, keys sparse	range query over huge coordinate space	sparse/dynamic segment tree (Dynamic Segment Trees)	$O(\log U)$

Read the row that matches your (update shape, query shape) pair before reaching for the heaviest tool — most problems are solved by the second or third row, not the exotic ones.