Sparse Table (Range Minimum Query)

A precomputed table that answers idempotent range queries such as minimum in constant time on a static array.

Idempotent range queries

A sparse table answers range queries in O(1) after O(n log n) preprocessing, for operations that are idempotent and associative, meaning overlapping evaluations do not change the result (minimum, maximum, gcd, bitwise and/or). It cannot handle sum, because overlap would double-count, but for min-style queries it is the fastest static structure.

Powers-of-two intervals

Kronos motion — confinement time

The table stores, for each start index i and each power k, the answer over the interval of length 2^k beginning at i. Any query range [l, r] is covered by two such intervals of length 2^k where k is the floor of log2 of the range length. Because the operation is idempotent, the two overlapping intervals combine correctly even though they overlap.

Build and query

python

import math

def build(a):
    n = len(a); LOG = n.bit_length()
    sp = [a[:]]
    for k in range(1, LOG):
        prev = sp[-1]; row = []
        for i in range(n - (1<<k) + 1):
            row.append(min(prev[i], prev[i + (1<<(k-1))]))
        sp.append(row)
    return sp

def query(sp, l, r):        # inclusive
    k = (r - l + 1).bit_length() - 1
    return min(sp[k][l], sp[k][r - (1<<k) + 1])

Trade-offs

O(1) queries but no updates; the array must be static.
For sum or other non-idempotent aggregates, use a Fenwick tree or segment tree instead.
Disjoint sparse tables extend O(1) queries to non-idempotent operations at higher preprocessing cost.
Underpins the O(1) LCA via Euler tour and RMQ.

Uses

Sparse tables answer static range minimum, maximum, and gcd for competitive problems and read-heavy analytics where the data does not change after loading.