SpecializedData structureaka RMQ table, doubling table

Sparse Table

A precomputed table of answers over power-of-two-length blocks that answers idempotent range queries (min, max, gcd) in O(1) after O(n log n) build, for static arrays.

▶ Visualize Pattern: Prefix Sum Practice (3)

Progress

Definition

A sparse table answers range queries on a static array — most famously range minimum (RMQ) — in O(1) per query after an O(n log n) preprocessing step. It works for any associative and idempotent operation: min, max, gcd, bitwise AND/OR. It does not support point updates; for a mutable array use a Segment Tree or Fenwick Tree.

The table st[k][i] stores the answer for the block of length 2^k starting at i: st[0][i] = a[i], and st[k][i] = op(st[k-1][i], st[k-1][i + 2^(k-1)]). A query [l, r] picks k = ⌊log₂(r - l + 1)⌋ and combines two overlapping blocks: op(st[k][l], st[k][r - 2^k + 1]). Overlap is harmless precisely because the operation is idempotent.

For non-idempotent operations like sum, the same table still works with an O(log n) query that decomposes the range into disjoint power-of-two blocks — but a Prefix Sum is simpler for that case.

range minimum querystatic arrayO(1) queryidempotentbinary lifting

Intuition

A mental model before the formal terms.

Suppose you want the shortest person in any contiguous group of a line-up, and the line-up never changes. Precompute the shortest in every group of 1, of 2, of 4, of 8, … starting at every position. Now for any range, pick the largest power-of-two group that fits, slide one copy to the left end and one copy to the right end. The two copies overlap in the middle, but that is fine — counting someone twice never changes who the shortest is.

That "counting twice is harmless" is idempotence, and it is why sums do not get the O(1) trick.

How it works

Build: K = ⌊log₂ n⌋ + 1 levels. st[0] = a. For k from 1 to K-1 and i from 0 while i + 2^k ≤ n: st[k][i] = op(st[k-1][i], st[k-1][i + 2^(k-1)]).
Log table: precompute lg[x] = ⌊log₂ x⌋ for x = 1…n with lg[x] = lg[x/2] + 1 to avoid floating point in queries.
Idempotent query(l, r): k = lg[r - l + 1]; return op(st[k][l], st[k][r - 2^k + 1]).
Non-idempotent query(l, r) (e.g. sum): walk k from high to low; if 2^k fits in the remaining range, fold st[k][l] and advance l += 2^k.
To return the index of the minimum (for LCA via Euler tour), store indices and compare a[idx].
Memory is n · log n entries; for n = 10^6 that is ~20 million values — fine for ints, watch it for objects.

Why it works

Any range [l, r] of length L is covered by the two blocks [l, l + 2^k - 1] and [r - 2^k + 1, r] with 2^k ≤ L < 2^(k+1), since 2 · 2^k > L. Idempotence (op(x, x) = x) and associativity/commutativity mean the overlap does not alter the result.

Each table cell is derived from two cells one level down, so building is O(n log n) and every cell is exactly the correct fold over its block by induction on k.

Operations

Operation	Description	Cost
build(a)	Fill st[k][i] level by level.	O(n log n)
query(l, r) — idempotent op	Two overlapping blocks.	O(1)
query(l, r) — general op	Decompose into disjoint blocks.	O(log n)
point update	Not supported; rebuild.	O(n log n)

Recognition

How to tell a problem wants this.

Many queries (q ≤ 10^5+) of range min/max/gcd/AND/OR on an array that never changes.
"Answer each query in O(1)" or tight time limits where a segment tree's log n per query is too slow.
Lowest common ancestor via Euler tour + RMQ.
Sliding-window min/max over arbitrary (not just fixed-size) windows.

“sum of subarray” → Prefix Sum “range query” → Segment / Fenwick Tree

Interactive demo

Play, step, change the input. ← → and space work too.

Array | queries — "numbers | query l r" — 0-based inclusive ranges

	0	1	2	3	4	5	6	7	8
k=0 (len 1)	·	·	·	·	·	·	·	·	·
k=1 (len 2)	·	·	·	·	·	·	·	·	·
k=2 (len 4)	·	·	·	·	·	·	·	·	·
k=3 (len 8)	·	·	·	·	·	·	·	·	·

1/26Build a sparse table for range-minimum over 9 values. Row k, column i will hold min(a[i .. i + 2^k − 1]) — every power-of-two-length block.

Cell being computed / answerInputs (two halves / two blocks)Computed

PseudocodeLearn Sparse Table →

1sp[0][i] = a[i]
2for k in 1..log n: for i while i + 2^k <= n:
3  sp[k][i] = min(sp[k-1][i], sp[k-1][i + 2^(k-1)])
4query(l, r): k = floor(log2(r - l + 1))
5  return min(sp[k][l], sp[k][r - 2^k + 1])   # two overlapping blocks

Variables

Complexity

access O(1)

search —

insert —

delete —

Speed

Pseudocode

1build: st[0] = a
2  for k in 1..K: for i in 0..n-2^k: st[k][i] = op(st[k-1][i], st[k-1][i + 2^(k-1)])
3lg[1] = 0; lg[x] = lg[x/2] + 1
4query(l, r): k = lg[r-l+1]; return op(st[k][l], st[k][r - 2^k + 1])

Implementation

1from typing import Callable
2 
3 
4class SparseTable:
5    """O(1) range queries for an idempotent op (min by default) on a static array."""
6 
71 · State — table st[k][i] = op over a[i .. i + 2^k - 1]
82 · Build in O(n log n)
9    def __init__(self, a: list[int], op: Callable[[int, int], int] = min):
10        self.op = op
11        n = len(a)
12        self.lg = [0] * (n + 1)  # lg[x] = floor(log2 x)
13        for i in range(2, n + 1):
14            self.lg[i] = self.lg[i // 2] + 1
15        K = self.lg[n] + 1 if n else 1
16        self.st = [list(a)]
17        for k in range(1, K):
18            prev = self.st[k - 1]
19            half = 1 << (k - 1)
20            self.st.append([op(prev[i], prev[i + half]) for i in range(n - (1 << k) + 1)])
21 
223 · O(1) query for idempotent ops (min/max/gcd) — overlapping halves are fine
23    def query(self, l: int, r: int) -> int:
24        """Inclusive range [l, r]."""
25        k = self.lg[r - l + 1]
26        return self.op(self.st[k][l], self.st[k][r - (1 << k) + 1])
27 
284 · O(log n) query for non-idempotent ops (sum) — disjoint blocks
29    def query_general(self, l: int, r: int, identity: int) -> int:
30        res = identity
31        k = len(self.st) - 1
32        while l <= r:
33            while k > 0 and l + (1 << k) - 1 > r:
34                k -= 1
35            res = self.op(res, self.st[k][l])
36            l += 1 << k
37        return res

Walkthrough

self.lg[i] = self.lg[i // 2] + 1 fills floor(log2) for every length up to n.
Each new row is a list comprehension over the previous row combining prev[i] and prev[i + half].
query looks up k = lg[r - l + 1] and combines two overlapping blocks — O(1) for min/max/gcd.
query_general shrinks k until a block fits, consumes it, and advances l — O(log n) for sum-like ops.
op defaults to the built-in min, which accepts exactly two arguments here.

Complexity (this implementation)

time O(n log n) build, O(1) query (idempotent) / O(log n) (general) · space O(n log n)

Python lists of lists cost ~28 bytes per int plus pointers; for large n use array or NumPy rows.

Language notes

math.gcd and operator.add are ready-made ops; gcd is idempotent, add is not.
The list comprehension in the build is much faster than an explicit loop with append.
1 << k works on unbounded ints, so there is no overflow concern for any table size.
For pure-min queries on mutable data, sortedcontainers or a segment tree is the practical choice.

Common mistakes in this language

Using math.log2 and int() per query — floating error can produce the wrong row for exact powers of two.
Calling query with a half-open r (exclusive) — the implementation is inclusive.
Passing sum as op — sum takes an iterable, not two scalars; use operator.add.

Language differences that matter here

C++ needs a lambda to wrap std::min as a default argument (overload set); JS/TS pass Math.min directly and Python passes min.
1 << k is 32-bit in JS/TS and int in C++; Python shifts are unbounded — none matters below 2^30 elements.
Python's sum is not a two-argument function; use operator.add. In C++ use std::plus<int>(), in JS/TS an arrow (a, b) => a + b.
Memory: C++ int rows are 4 bytes/element, JS/TS numbers 8 bytes (or 4 with Int32Array), Python lists ~36 bytes/element.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	st[0][i] is the original array.
Search	—	—
Insert	—	—	Static; rebuild O(n log n).
Delete	—	—	Static; rebuild O(n log n).
Update	O(n log n)	O(n log n)	Full rebuild.
Build	O(n log n)	O(n log n)
Range min query	O(1)	O(1)	Any idempotent op.
Range query (general op)	O(log n)	O(log n)
Space	O(n log n)

Advantages & disadvantages

Advantages

True O(1) queries — nothing beats it for static RMQ in practice.
Simple to implement (two nested loops for the build, three lines per query).
Works for any idempotent associative operation, and with O(log n) queries for any associative one.

Disadvantages

Static: any update forces an O(n log n) rebuild.
O(n log n) memory versus O(n) for a segment tree or Fenwick tree.
O(1) query needs idempotence; range sums require O(log n) or a prefix-sum.

Use cases

Range minimum / maximum queries on immutable arrays.
LCA queries: RMQ over the Euler tour depths.
Range GCD, range bitwise AND/OR.
Binary-lifting-style "jump 2^k steps" tables share the same doubling structure.
Suffix-array LCP queries between arbitrary suffixes.

Use it when

Static array with many range min/max/gcd/AND/OR queries.
Query time must be O(1).
LCA via Euler tour when the tree is static.

Avoid it when

The array changes — use a Segment Tree (or Fenwick Tree for prefix-invertible ops).
Range sums — a Prefix Sum array is O(n) space and O(1) query.
Memory is tight and n log n values do not fit.
Only a handful of queries — a linear scan per query is simpler.

Alternatives

Segment Tree Fenwick Tree Prefix Sum Monotonic Queue

Common mistakes

Using the two-overlapping-blocks query for sums (double counts the overlap).
Building rows for i where i + 2^k > n — index out of range.
Computing k with floating-point log2 in a hot loop — precompute an integer log table.
Off-by-one: the second block starts at r - 2^k + 1, not r - 2^k.
Forgetting that the table is static and mutating the underlying array.

Interview patterns

Range minimum query with 10^5 queries on a fixed array.
Sliding Window Maximum over arbitrary windows (fixed windows are better with a Monotonic Queue).
LCA in a static tree via Euler tour + RMQ.
Number of subarrays with GCD/AND equal to k using range queries plus binary search.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Recognizing a sliding-window problemIntermediate
Prefix sum or segment tree?Intermediate

Mock interviews

Minimum Size Subarray SumIntermediate
Subarray Sum Equals KIntermediate

Interview problems

Sliding Window Maximumhard Lowest Common Ancestor of a Binary Treemedium Range Sum Query — Mutablemedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related