Sparse Table

$O (1)$ range queries on a static array, for idempotent operations. $O (n lo g n)$ preprocessing and memory.

The structure

$sp [k] [i]$ = the aggregate of the range $[i, i + 2^{k})$ .

$sp [0] [i] = a_{i}, sp [k] [i] = op (sp [k - 1] [i], sp [k - 1] [i + 2^{k - 1}]) .$

const int LOG = 20;
int sp[LOG][MAXN], lg[MAXN];
 
void build(vector<int>& a) {
    int n = a.size();
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
    for (int i = 0; i < n; i++) sp[0][i] = a[i];
    for (int k = 1; k < LOG; k++)
        for (int i = 0; i + (1 << k) <= n; i++)
            sp[k][i] = min(sp[k-1][i], sp[k-1][i + (1 << (k-1))]);
}
 
int query(int l, int r) {                    // inclusive [l, r]
    int k = lg[r - l + 1];
    return min(sp[k][l], sp[k][r - (1 << k) + 1]);
}

The query covers $[l, r]$ with two overlapping blocks of length $2^{k}$ . Overlap is why the operation must be idempotent.

Idempotence — which operations work

Operation	$x op x = x$ ?	Sparse table?
$min$ , $max$	yes	✔ $O (1)$
$g cd$ , $lcm$	yes	✔ $O (1)$ (with a $lo g$ for the gcd itself)
bitwise AND, OR	yes	✔ $O (1)$
$+$ , $\times$ , XOR	no	✘ — double-counts the overlap

For non-idempotent operations use a disjoint sparse table ( $O (1)$ query, non-overlapping blocks) or a segment tree.

Choosing a range-query structure

Updates	Operation	Structure	Query
none	idempotent	sparse table	$O (1)$
none	any associative	disjoint sparse table	$O (1)$
none	sum	prefix sum	$O (1)$
point	invertible	Fenwick	$O (lo g n)$
point/range	any associative	segment tree	$O (lo g n)$
—	RMQ, $O (n)$ build	Farach-Colton-Bender	$O (1)$

Sparse tables are the right default whenever the array never changes: the constant factor is tiny and the code is fifteen lines.

Uses

LCA via Euler tour + RMQ on depths — the fastest practical LCA
LCP of arbitrary suffixes — RMQ over the LCP array
Range GCD queries
Binary lifting is structurally the same doubling table, applied to a tree instead of an array
Static range min for two-pointer / divide-and-conquer algorithms

2D sparse table

$sp [k_{1}] [k_{2}] [i] [j]$ over rectangles of size $2^{k_{1}} \times 2^{k_{2}}$ . Build $O (nm lo g n lo g m)$ , query $O (1)$ with four overlapping rectangles. Memory is the problem — a $1000 \times 1000$ grid needs $1 0^{8}$ entries. Usually a sqrt decomposition or per-row sparse tables are more practical.

Memory

$O (n lo g n)$ ints. For $n = 1 0^{6}$ and $LOG = 20$ that is 80 MB — often too much. Fixes: reduce LOG to $⌈ lo g_{2} n ⌉ + 1$ , use int not long long, or switch to a segment tree ( $O (n)$ memory, $O (lo g n)$ query).

whoashish's cp notes

Directory