What is the Sparse Table Technique?
Learn how the sparse table technique answers range min/max queries in O(1) time with O(n log n) preprocessing.
Expected Interview Answer
A sparse table is a precomputed 2D array that answers range minimum, maximum, or GCD queries on a static array in O(1) time after O(n log n) preprocessing, by storing the answer for every range whose length is a power of two.
The table entry table[k][i] holds the answer (e.g. minimum) for the range starting at index i with length 2^k, built from two half-length ranges: table[k][i] combines table[k-1][i] and table[k-1][i + 2^(k-1)]. To answer an arbitrary range query [L, R], pick the largest power of two k that fits within the range length, and combine the two overlapping ranges of length 2^k starting at L and ending at R — overlap is fine for idempotent operations like min, max, and GCD, which is why this only works for such operations, not for sum. Because the answer set is precomputed for all power-of-two ranges, any query becomes a single lookup and comparison, giving O(1) query time at the cost of O(n log n) space and preprocessing. It is the go-to structure when the array never changes but range-min or range-max queries must be answered thousands of times.
- O(1) query time after preprocessing
- O(n log n) preprocessing time and space
- Ideal for immutable arrays with many repeated queries
- Works for any idempotent operation: min, max, GCD, AND, OR
AI Mentor Explanation
A statistician precomputes the best strike rate over every power-of-two-length stretch of an innings — 1 ball, 2 balls, 4 balls, 8 balls, and so on — storing each result in a table before the match analysis begins. When asked for the best strike rate over any arbitrary stretch of overs, they pick the two largest precomputed power-of-two stretches that together cover the whole range, even if they overlap, and just compare those two stored answers. Because 'best strike rate' doesn't change if you double-count some balls, overlapping stretches cause no error. This lets the statistician answer any of thousands of stretch queries instantly, having done all the heavy lifting once upfront.
Step-by-Step Explanation
Step 1
Precompute powers of two ranges
For each k from 0 to log n, compute table[k][i] = combine(table[k-1][i], table[k-1][i + 2^(k-1)]) for every valid i.
Step 2
Base case k = 0
table[0][i] equals the array value at index i, representing a range of length 1.
Step 3
Answer a query [L, R]
Let k = floor(log2(R - L + 1)); the answer is combine(table[k][L], table[k][R - 2^k + 1]).
Step 4
Rely on idempotency
Because min/max/GCD give the same result even if the two chosen ranges overlap, no extra bookkeeping is needed for overlap.
What Interviewer Expects
- Explain the table[k][i] recurrence and its base case
- Justify O(1) queries via choosing overlapping power-of-two ranges
- State this only works for idempotent operations (min, max, GCD), not sum
- Give the O(n log n) preprocessing time and space cost
Common Mistakes
- Trying to use a sparse table for range sum, where overlap breaks correctness
- Forgetting to precompute log2 values, causing slow per-query log computation
- Off-by-one errors in the second range start index (R - 2^k + 1)
- Assuming sparse tables support updates, when they only work for static (immutable) arrays
Best Answer (HR Friendly)
“A sparse table precomputes answers for every power-of-two-length range so I can answer range min or max queries instantly afterward. I would reach for it whenever the data is fixed and I know I'll be asked the same type of range query many times, trading extra memory upfront for O(1) lookups later.”
Code Example
import math
def build_sparse_table(arr):
n = len(arr)
k = arr[0].bit_length() if False else int(math.log2(n)) + 1
table = [[0] * n for _ in range(k)]
table[0] = arr[:]
for level in range(1, k):
length = 1 << level
half = 1 << (level - 1)
for i in range(n - length + 1):
table[level][i] = min(table[level - 1][i], table[level - 1][i + half])
return table
def query_min(table, log_table, left, right):
level = log_table[right - left + 1]
length = 1 << level
return min(table[level][left], table[level][right - length + 1])
def build_log_table(n):
log_table = [0] * (n + 1)
for i in range(2, n + 1):
log_table[i] = log_table[i // 2] + 1
return log_tableFollow-up Questions
- Why can a sparse table not efficiently support range sum queries?
- How would you support point updates alongside range min queries instead?
- How does a sparse table compare to a segment tree for static range queries?
- How would you extend a sparse table to two dimensions for a grid?
MCQ Practice
1. What is the query time complexity of a sparse table after preprocessing?
Because the operation is idempotent, two overlapping precomputed ranges answer any query in constant time.
2. Which operation is NOT suitable for a classic sparse table?
Sum is not idempotent, so overlapping ranges would double-count elements and give a wrong answer.
3. What is the preprocessing time complexity of building a sparse table for n elements?
Building log n levels, each requiring O(n) work to fill, gives O(n log n) total preprocessing time.
Flash Cards
What does table[k][i] store in a sparse table? — The combined answer (e.g. min) for the range starting at i with length 2^k.
Why must the operation be idempotent for a sparse table? — Because query ranges may overlap, and idempotent operations give the same result despite double-counting.
What is the query time complexity of a sparse table? — O(1), after O(n log n) preprocessing.
Can a sparse table be updated after construction? — No — it is built for static, immutable arrays only.