Data Structures
Sparse Table
Difficulty: Advanced
Range minimum queries on a fixed array do not need updates, so the segment tree's O(log n) query is leaving performance on the table. A Sparse Table flattens the query down to genuine O(1): precompute the minimum of every power-of-2...
Sparse Table
Range minimum queries on a fixed array do not need updates, so the segment tree's O(log n) query is leaving performance on the table. A Sparse Table flattens the query down to genuine O(1): precompute the minimum of every power-of-2 length window, and any range [L, R] can be answered by combining two such windows that together cover it, exploiting the fact that min(min(A), min(B)) = min(A union B) when the windows overlap.
This lesson covers the O(n log n) preprocessing that fills a 2D table indexed by (start, log2_length), the O(1) query trick for idempotent operations such as min, max, GCD, and bitwise OR, the log2_floor precomputation that makes every query branch-free, and the slower O(log n) query needed when the operation is not idempotent (like sum). You will see why this structure is the right tool for the Range Minimum Query (RMQ) problem and an essential building block in algorithms like Lowest Common Ancestor in O(1) per query.
In Arrays & Strings, a flat array stored values; here the same shape stores precomputed answers indexed by a length exponent. Logarithms & Exponentiation is what makes the geometry work: power-of-two windows tile the index space the way binary representations tile integers, and the O(1) query depends on floor(log2(length)).
With Sparse Tables in your toolkit, the curriculum next pivots to specialized structures for strings, immutability, and bounded integer universes.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the static range query problem and why Sparse Tables are optimal for idempotent operations on static arrays.
Build the Sparse Table preprocessing matrix in O(n log n) time using dynamic programming on interval lengths.
Answer range minimum queries in O(1) by overlapping two precomputed power-of-2 ranges.
Distinguish idempotent operations (min, max, GCD, OR) from non-idempotent ones (sum) and explain why the O(1) trick requires idempotency.
Analyze time and space complexity of Sparse Table construction and queries.
Compare Sparse Tables with Segment Trees and Fenwick Trees to decide when each is the right tool.
Why This Matters
01
Sparse Tables achieve O(1) range minimum/maximum queries on static data, which no other general-purpose structure can match. Segment trees require O(log n) per query and Fenwick Trees cannot answer arbitrary range min/max queries at all.
02
The Range Minimum Query (RMQ) problem solved by Sparse Tables is a fundamental building block in advanced algorithms including Lowest Common Ancestor (LCA) on trees, suffix array construction, and Cartesian tree applications.
03
Understanding Sparse Tables deepens your grasp of how idempotent operations (where applying an operation twice yields the same result) enable algorithmic shortcuts that non-idempotent operations cannot exploit.
04
Sparse Tables appear in competitive programming contests when you need sub-logarithmic query performance on static data, and they are used in production systems for static lookup tables in networking and database query optimization.
Key Terms
7 terms you'll encounter in this lesson
Sparse Table
A data structure that preprocesses a static array into a 2D table where entry table[k][i] stores the answer (min, max, GCD, etc.) for the subarray starting at index i with length 2^k. Enables O(1) range queries for idempotent operations.
Range Minimum Query (RMQ)
A query that asks: 'What is the minimum value in the subarray from index L to index R?' Sparse Tables answer RMQ in O(1) after O(n log n) preprocessing.
Idempotent Operation
An operation f where applying it to overlapping ranges gives the correct result: f(a, a) = a. Examples: min, max, GCD, bitwise OR, bitwise AND. Contrast with sum, where overlapping ranges cause double-counting.
Power-of-2 Range
A subarray whose length is exactly 2^k for some integer k. Sparse Tables precompute answers for all such ranges. Any range [L, R] can be covered by at most two overlapping power-of-2 ranges.
Floor Log2
The largest integer k such that 2^k <= n. Used to determine which precomputed power-of-2 range to use for a query. Computed as floor(log2(R - L + 1)) for a range of length R - L + 1.
Overlap Trick
The key insight enabling O(1) queries: for idempotent operations, the answer for range [L, R] equals f(table[k][L], table[k][R - 2^k + 1]) where k = floor(log2(R - L + 1)). The two power-of-2 ranges may overlap, but because the operation is idempotent, overlapping elements do not affect the result.
Static Array
An array whose elements do not change after the data structure is built. Sparse Tables only work on static arrays; if elements change, a Segment Tree or Fenwick Tree is needed.
Heads Up
Common misconceptions to watch out for
"Sparse Tables can answer range sum queries in O(1)"
The O(1) overlap trick only works for idempotent operations (min, max, GCD). For sum, the overlapping ranges would double-count elements. Sum queries on a Sparse Table require O(log n) time by using non-overlapping power-of-2 ranges (like binary decomposition), making prefix sums or Fenwick Trees a better choice.
"Sparse Tables support updates like Segment Trees"
Sparse Tables are strictly for static data. If you update even one element, you must rebuild the entire table in O(n log n) time. For dynamic data, use a Segment Tree (O(log n) updates) or Fenwick Tree.
"The two ranges in a query must not overlap"
Overlap is not only allowed but essential for the O(1) trick. Because min(a, a) = a (idempotency), processing the same element twice does not change the result. This is what makes the trick possible.
"Sparse Tables use O(n^2) space because they store all pairs"
Sparse Tables use O(n log n) space. They only store answers for power-of-2 length ranges (lengths 1, 2, 4, 8, ...), not all possible ranges. There are log2(n) possible lengths and n starting positions, giving n * log2(n) entries total.