Sparse Tables and Range Minimum Query

Range Minimum Query (RMQ) asks: given an array that never changes, answer thousands of “what’s the smallest value between index l and r?” questions as fast as possible. A segment tree answers each query in $O(\log n)$ — fast, but not the fastest possible. When the array is static (no updates, ever) and the operation is idempotent (like min, max, or gcd), a sparse table answers every query in $O(1)$ after one $O(n \log n)$ preprocessing pass. This is one of the first “free speedups” competitive programmers reach for the moment updates aren’t in the problem.

What you’ll learn

• The RMQ problem and why a static array unlocks a faster structure than a segment tree.
• Building a sparse table: precomputing the answer for every range whose length is a power of two.
• Answering a query in $O(1)$ by covering [l, r] with two overlapping power-of-two ranges — and why the overlap is completely harmless for idempotent operations.
• Why sparse tables can’t support updates, unlike a segment tree or Fenwick tree.
• The brief connection between RMQ and LCA (lowest common ancestor) via an Euler tour.

The cue

You are looking at a sparse table when…

• The array is static — it never changes between queries — and you need range min, max, or gcd many times. A single query is $O(1)$ after an $O(n \log n)$ build.
• The problem says ”$q$ queries” with $q$ around $10^5$ and no updates. That combination is the tell: preprocessing is worth it, mutability is not needed.
• You are building LCA by Euler tour, where the reduction turns ancestor queries into range minimum over a depth array.
• The operation is idempotent — min(x, x) == x — so overlapping the two query windows is harmless. That is the precondition, and it is what buys the $O(1)$.

The reframe: precompute the answer for every range whose length is a power of two. Any range is then covered by exactly two such windows, overlapping in the middle, and because min and max do not care about double-counting, one comparison answers the query. No tree, no recursion, no per-query loop.

Reach for something else when the array changes (a segment tree — a sparse table cannot be updated without rebuilding it), or when the operation is not idempotent: sums double-count on the overlap, so a range sum wants a plain prefix-sum array ($O(1)$ anyway) or a Fenwick tree if updates arrive.

Building the table: powers of two

For every starting index i and every power j, precompute the answer for the range that starts at i and spans $2^j$ elements:

$$st[j][i] = \text{op}\bigl(st[j-1][i],\ st[j-1][i + 2^{j-1}]\bigr)$$

Row 0 is just the array itself (ranges of length $2^0 = 1$). Row j is built from row j - 1 by combining two halves that are each $2^{j-1}$ long — so the whole table is $\log n$ rows deep, each row an array scan: $O(n \log n)$ total.

sparse_table_min.py

def build_log_table(n):
    log = [0] * (n + 1)
    for i in range(2, n + 1):
        log[i] = log[i // 2] + 1        # log[i] = floor(log2(i)), built incrementally
    return log
 
 
def build_sparse_table(arr):
    n = len(arr)
    log = build_log_table(n)
    k = log[n] + 1                       # number of rows needed
    st = [arr[:]]                        # st[0] = ranges of length 2^0 = 1
    for j in range(1, k):
        half = 1 << (j - 1)              # length of each half: 2^(j-1)
        row = []
        for i in range(n - (1 << j) + 1):
            row.append(min(st[j - 1][i], st[j - 1][i + half]))
        st.append(row)
    return st, log
 
 
def query_min(st, log, l, r):
    """Inclusive range [l, r], 0-indexed."""
    j = log[r - l + 1]
    return min(st[j][l], st[j][r - (1 << j) + 1])
 
 
arr = [7, 2, 3, 0, 5, 10, 3, 12, 18]
st, log = build_sparse_table(arr)
 
print("min of [1, 5]:", query_min(st, log, 1, 5))   # expect 0
print("min of [3, 3]:", query_min(st, log, 3, 3))   # expect 0
print("min of [6, 8]:", query_min(st, log, 6, 8))   # expect 3

Querying in O(1): two overlapping windows

A query [l, r] of length len is covered by two windows of length $2^j$ where $j = \lfloor \log_2(\text{len}) \rfloor$: one starting at l, one ending at r. These two windows almost always overlap in the middle — and that overlap is exactly why this only works for idempotent operations. min(min(x, x), y) == min(x, y), so double-counting the overlapping middle changes nothing. The same trick would silently break for sum, which double-counts real values.

sketch The two overlapping power-of-two windows that cover a query p5.js Pause Restart

Blue = the window starting at l. Pink = the window ending at r. Gold = where they overlap -- harmless for min/max/gcd, but WRONG for sum.

Note that j is looked up from a precomputed log table in O(1) — recomputing math.log2 on every query would still be O(1) in theory but slower in practice and prone to floating-point edge cases at exact powers of two.

The same idea works for any idempotent, associative operation — swap min for max or math.gcd and everything else stays identical:

sparse_table_gcd.py

import math
 
 
def build_sparse_table_gcd(arr):
    n = len(arr)
    log = [0] * (n + 1)
    for i in range(2, n + 1):
        log[i] = log[i // 2] + 1
    k = log[n] + 1
    st = [arr[:]]
    for j in range(1, k):
        half = 1 << (j - 1)
        row = []
        for i in range(n - (1 << j) + 1):
            row.append(math.gcd(st[j - 1][i], st[j - 1][i + half]))
        st.append(row)
    return st, log
 
 
def query_gcd(st, log, l, r):
    j = log[r - l + 1]
    return math.gcd(st[j][l], st[j][r - (1 << j) + 1])
 
 
arr = [12, 18, 30, 42, 8, 16]
st, log = build_sparse_table_gcd(arr)
 
print("gcd of [0, 2]:", query_gcd(st, log, 0, 2))   # gcd(12, 18, 30) = 6
print("gcd of [3, 5]:", query_gcd(st, log, 3, 5))   # gcd(42, 8, 16) = 2

Why sparse tables can’t support updates

Every cell st[j][i] was combined from overlapping ranges built out of earlier rows — changing one element of the original array would require recomputing every st[j][i] whose range includes that index, at every level j. That’s O(n log n) work per update, which defeats the purpose. A segment tree rebuilds only the O(log n) ancestors of the changed leaf, and a Fenwick tree (Binary Indexed Tree) updates prefix aggregates in O(log n) too — both are the right tool the moment the array can change. Sparse tables are strictly a static-array optimization.

The RMQ — LCA connection

Finding the lowest common ancestor of two nodes in a tree can be reduced to a Range Minimum Query: do an Euler tour of the tree (recording each node’s depth as you enter and backtrack), and the LCA of two nodes is the shallowest node between their two positions in that tour — exactly an RMQ. Building a sparse table over the Euler tour’s depth array answers any LCA query in O(1) after O(n log n) preprocessing, which is why sparse tables show up constantly in tree problems, not just flat arrays.

Dry run

arr = [7, 2, 3, 0, 5, 10, 3, 12, 18], range minimum. Row j holds the minimum of every window of length $2^j$:

row	window length	contents
j=0	1	7 2 3 0 5 10 3 12 18 — the array itself
j=1	2	2 2 0 0 5 3 3 12
j=2	4	0 0 0 0 3 3
j=3	8	0 0

Each row is built from the one above by combining two halves: st[2][4] = min(st[1][4], st[1][6]) = min(5, 3) = 3. Rows get shorter because a window of length $2^j$ starting at i must fit — $n - 2^j + 1$ entries.

Query [2, 7] inclusive — six elements: 3 0 5 10 3 12, minimum 0.

step	value
length	7 − 2 + 1 = 6
j = floor(log2(6))	2 — the largest power of two that fits
left window	st[2][2] = min of arr[2..5] = 0
right window	st[2][7 − 4 + 1] = st[2][4] = min of arr[4..7] = 3
answer	min(0, 3) = 0 ✓

• The two windows overlap — arr[4..5] is in both — and that is fine only because min is idempotent. Counting an element twice does not change a minimum. Try the same structure for a range sum and the overlap is added twice, which is why sums use prefix arrays instead. This is the single most important sentence about sparse tables.
• Two lookups, no loop. The query does not depend on the range length at all: any range, however long, is two array reads and one comparison. That is the $O(1)$.
• j is the largest power of two that fits, not the smallest that covers. Length 6 uses windows of 4, which together span 8 positions — deliberately more than the range, anchored at both ends so the union is exactly [2, 7].
• Precompute the logs. log[i] = log[i // 2] + 1 builds the whole table in one $O(n)$ pass; calling math.log2 per query is slower and invites floating-point edge cases at exact powers of two.

Complexity

Structure	Build	Query	Update	Best for
Sparse table	$O(n \log n)$	$O(1)$	Not supported	Static array, idempotent op (min/max/gcd)
Segment tree	$O(n)$	$O(\log n)$	$O(\log n)$	Any associative op, array does change
Fenwick tree (BIT)	$O(n)$	$O(\log n)$	$O(\log n)$	Prefix sums and sum-like aggregates

When to reach for a sparse table

The instant a problem statement says the array is fixed for the whole run and asks for many range-min/max/gcd queries, a sparse table is the fastest correct answer — $O(1)$ per query beats a segment tree’s $O(\log n)$ every time. The moment you see the word “update” anywhere in the problem, drop straight to a segment tree instead.

The variant map

Need	Structure	Query	Note
Static range min / max	sparse table	$O(1)$	the base case; overlap is free
Static range gcd	sparse table	$O(1)$	gcd is idempotent too — gcd(x, x) = x
Static range sum	prefix-sum array	$O(1)$	not a sparse table: sums double-count the overlap
Static range sum, if you insist	sparse table with disjoint windows	$O(\log n)$	possible, but the prefix array is strictly better
Mutable range min	segment tree	$O(\log n)$	a sparse table cannot be updated without a rebuild
Mutable range sum	Fenwick tree	$O(\log n)$	invertible, so prefix subtraction works
LCA on a static tree	Euler tour → RMQ over depths	$O(1)$ per query	the classic reduction; compare binary lifting at $O(\log n)$
2-D static range min	sparse table over both dimensions	$O(1)$	$O(nm \log n \log m)$ memory — usually too much
Range min with few queries	just loop the range	$O(\text{len})$	below ~$\log n$ queries the build never pays for itself
Sliding window min (fixed width)	monotonic deque	$O(n)$ total	beats both when the window only moves forward

Interview follow-ups

They ask	What they’re checking	The answer
“Why can the two query windows overlap?”	The precondition	Because min is idempotent — counting an element twice does not change the answer. That is exactly why the same structure cannot answer range sums
“Sparse table or segment tree?”	Judgement	Sparse table if the array is static: $O(1)$ per query beats $O(\log n)$. Segment tree the moment anything is updated — a sparse table has no update, only a full $O(n\log n)$ rebuild
“What is the preprocessing cost, and when is it worth it?”	Cost modelling	$O(n \log n)$ time and memory. It pays off once the query count exceeds roughly $\log n$; for a handful of queries, scanning the range directly is cheaper and simpler
“How do you compute j fast?”	Practical detail	Precompute log[i] = log[i // 2] + 1 in one $O(n)$ pass. math.log2 per query is slower and can misbehave at exact powers of two
“Range sum with a sparse table?”	The trap	Not with overlapping windows — the intersection is counted twice. Use a prefix-sum array ($O(1)$, less memory), or disjoint sparse-table windows at $O(\log n)$
“Reduce LCA to RMQ”	Composition	Euler-tour the tree recording depth at each visit; the LCA of u and v is the shallowest node in the depth array between their first occurrences — a range minimum, so $O(1)$ per query after the build
“Memory is tight at $n = 10^6$”	Scale sense	The table is $n \log n$ entries — about 20 million at $n = 10^6$, likely too much. Use a segment tree ($2n$), or block decomposition / sqrt decomposition if $O(\sqrt n)$ queries are acceptable
“The window slides forward one step at a time”	Choosing the cheaper tool	A monotonic deque gives all window minima in $O(n)$ total with $O(k)$ space — no preprocessing at all. Sparse tables are for arbitrary ranges, not sliding ones

Practice — real LeetCode problems

Sparse tables answer idempotent range queries — min, max, gcd, AND, OR — in $O(1)$ after an $O(n \log n)$ build. These three are all “range something over a window”, and each has a cheaper structure hiding behind it. Learning to spot the cheaper one is as valuable as knowing the table.

LC 2419 — Longest Subarray With Maximum Bitwise AND · Medium

Problem. Among all subarrays, consider those whose bitwise AND is the largest achievable. Return the length of the longest such subarray.

Constraints. 1 <= len(nums) <= 10**5, 1 <= nums[i] <= 10**6.

Examples. [1,2,3,3,2,2] gives 2 — the maximum AND is 3, from [3,3] · [1,2,3,4] gives 1

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Included as a deliberate anti-lesson: this problem looks like range-AND queries and is actually two lines.

The argument. For any subarray, a & b <= min(a, b), because AND only ever clears bits. So every subarray’s AND is at most max(nums). Can that be achieved? Yes — a length-1 subarray holding the maximum. And it is achieved only by subarrays whose every element equals the maximum, since including anything smaller would drop the value below it. Therefore the answer is the longest run of the maximum.

Time $O(n)$, two passes. Space $O(1)$.

• Runs, not counts. [1,2,3,3,2,2] has two 3s and they happen to be adjacent; if the input were [3,1,3] the answer would be 1, not 2. Counting occurrences instead of measuring runs is the wrong answer.
• The maximum can be unique, giving 1 — as in [1,2,3,4].
• All equal gives the whole length.
• nums[i] >= 1 by constraint, so there is no zero-versus-empty subtlety.

When a sparse table would actually be needed. If the question asked for the AND of arbitrary given ranges, or for the longest subarray whose AND equals some target, the bound no longer collapses the problem. Then either build a sparse table — AND is idempotent and associative, so overlapping windows are safe — or use the set-of-window-values trick from the next problem.

Follow-ups you should expect: “Longest subarray with maximum bitwise OR?” — different: OR only ever sets bits, so the maximum is the OR of the whole array and the answer relates to the shortest prefix achieving it. “Maximum AND of exactly k elements?” — a greedy from the high bit down, keeping candidates. “Arbitrary range-AND queries?” — sparse table, $O(1)$ per query. “The subarray with AND closest to a target?” — the next problem.

LC 1521 — Find a Value of a Mysterious Function Closest to Target · Hard

Problem. The function computes the bitwise AND of a subarray arr[l..r]. Return the minimum possible value of abs(func(arr, l, r) - target) over all subarrays.

Constraints. 1 <= len(arr) <= 10**5, 1 <= arr[i] <= 10**6, 0 <= target <= 10**7.

Examples. arr = [9,12,3,7,15], target = 5 gives 2 · arr = [1000000,1000000,1000000], target = 1 gives 999999 · arr = [1,2,4,8,16], target = 0 gives 0

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The technique — maintain the set of results of all subarrays ending at i — works for any operator that is monotone in one direction. AND qualifies: extending a subarray leftward can only clear bits, so along the chain of subarrays ending at i the value only ever loses bits.

Why the set is small. Order those subarrays by increasing length; each AND is a submask of the previous, so each distinct value drops at least one bit. With values under $10^6$ that is at most 20 bits, so at most about 20 distinct values at any index — independent of n.

Time $O(n \log(\max))$, roughly $2 \times 10^6$ operations. Space $O(\log \max)$.

• {n} | ... is what starts the length-1 subarray at i. Omitting it misses every single-element answer, including the whole third example.
• Check the value as you generate it. The best answer may come from any length, not just the longest.
• Monotonicity does not give you binary search. The values decrease along the chain, but abs(v - target) is not monotone, so you must examine all of them — a subtle point and a common wrong optimisation.
• A single element returns abs(arr[0] - target), and the initialisation handles it before the loop.
• [1000000]*3 with target 1 gives 999999: every AND equals 1000000, and nothing gets closer.

The sparse-table alternative. Build a sparse table for range AND, then for each left endpoint binary search the right endpoint — valid because the AND is monotone non-increasing in r. That is $O(n \log^2 n)$ and is the answer if you are asked to “use a sparse table”. The set method is faster and shorter, but knowing both, and knowing that the monotonicity is what licenses the binary search, is the complete answer.

Follow-ups you should expect: “OR instead of AND?” — the same technique; OR only sets bits, so the set is still $O(\log \max)$. “GCD of a subarray closest to a target?” — also works, since each step at least halves the gcd. “Sum instead?” — breaks completely: sums do not lose bits, so the set is $O(n)$. Use prefix sums plus a sorted structure. “Count the subarrays whose AND equals a target?” — carry counts alongside the set values.

LC 1793 — Maximum Score of a Good Subarray · Hard

Problem. The score of a subarray nums[i..j] is min(nums[i..j]) * (j - i + 1). A subarray is good if i <= k <= j. Return the maximum score of a good subarray.

Constraints. 1 <= len(nums) <= 10**5, 1 <= nums[i] <= 2 * 10**4, 0 <= k < len(nums).

Examples. nums = [1,4,3,7,4,5], k = 3 gives 15 — the subarray [4,3,7,4,5] has minimum 3 and length 5 · nums = [5,5,4,5,4,1,1,1], k = 0 gives 20

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Every good subarray contains k, so the family of candidates is nested: exactly one window of each width from 1 to n is worth considering, and the greedy visits precisely those.

Why expanding toward the taller neighbour is safe. Suppose the optimal window has width w. The greedy also produces some window of width w, and at every step it chose the neighbour that keeps the running minimum as high as possible. By induction, the greedy’s window of width w has a minimum at least as large as any other width-w window containing k — and since the score is minimum × width, at equal width the higher minimum wins. So the greedy’s width-w window scores at least as well as the optimum, and it was considered. That exchange argument is what an interviewer is listening for; the code is easy.

Time $O(n)$. Space $O(1)$.

• Update floor with both ends, min(floor, nums[left], nums[right]). Only one moved, but writing both is harmless and removes a branch you can get wrong.
• >= versus > in the tie-break does not matter — with equal neighbours either choice leaves the minimum unchanged.
• The boundary guards come first. Once one side is exhausted the other must move, and testing left == 0 before comparing avoids indexing at -1, which in Python would silently read the last element rather than crash. That is a genuinely dangerous bug here.
• A single element returns nums[0] and the loop never runs.
• k = 0 works with no special case; the left guard fires immediately.

Two other solutions worth naming. A monotonic stack finds, for each element as the minimum, the widest window in which it is the minimum — keep those windows that contain k. Or binary search plus a sparse table: for each candidate minimum, find the widest range where all values are at least it. Both are $O(n \log n)$ or $O(n)$ and are the standard alternatives; the two-pointer greedy is the shortest.

Follow-ups you should expect: “Without the constraint that the window contains k?” — that is Largest Rectangle in Histogram, so monotonic stack. “Maximise min × length for exactly length w?” — sliding-window minimum with a deque. “Sum instead of minimum?” — prefix sums, a completely different problem. “Prove the greedy?” — the exchange argument above; be ready, because “why is this not just a guess” is the follow-up on every greedy.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

2 problems

1 easy0 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○303Range Sum Query - Immutableeasy(Easy) -- the non-idempotent analog: since `sum` isn't idempotent, a plain prefix-sum array (not a sparse table) is the right $O(1)$-query structure for a static array of sums
• ○239Sliding Window Maximumhard(Hard) -- a *different* tool for a *different* shape of problem: the window slides by one each step instead of jumping to arbitrary `[l, r]` pairs, so a monotonic deque wins here over a sparse tableNeetCode 150amazongooglebytedance

Self-check

pch.quizTag Sparse tables and RMQ — self-check

1. Why is it safe for the two query windows to overlap?

   A They are constructed never to overlap B Because min is idempotent — min(x, x) = x — so counting the overlapping elements twice cannot change the answer C Because the overlap is subtracted afterwards D Because the windows are always adjacent
   pch.quizShowAnswer

   B — Because min is idempotent — min(x, x) = x — so counting the overlapping elements twice cannot change the answer — This single property is what buys the O(1) query, and it is exactly why the same structure cannot answer range sums: the overlap would be added twice.

2. Can a sparse table answer range SUM queries in O(1)?

   A Yes, identically to min B No — sums are not idempotent, so the overlapping windows double-count. Use a prefix-sum array, which is O(1) anyway and uses less memory C Yes, if the values are positive D Yes, by dividing the overlap by two
   pch.quizShowAnswer

   B — No — sums are not idempotent, so the overlapping windows double-count. Use a prefix-sum array, which is O(1) anyway and uses less memory — Disjoint-window sparse tables can do sums at O(log n), but there is no reason to: prefix sums already answer static range sums in O(1) with O(n) memory.

3. For the range [2, 7] (length 6), which j does the query use and why?

   A j = 3, the smallest power of two that covers 6 B j = 2, the LARGEST power of two that FITS — two windows of length 4 anchored at each end cover [2,7] exactly, overlapping in the middle C j = 6, the length itself D j = 1, because 6 is even
   pch.quizShowAnswer

   B — j = 2, the LARGEST power of two that FITS — two windows of length 4 anchored at each end cover [2,7] exactly, overlapping in the middle — The two windows span 8 positions between them, deliberately more than the range; anchoring at both ends makes their union exactly the range.

4. The array will be updated between queries. Sparse table?

   A Yes, update the affected rows B No — there is no update operation; a change invalidates O(n log n) precomputed windows, so you would rebuild from scratch. Use a segment tree C Yes, if updates are rare D Yes, rebuild only row 0
   pch.quizShowAnswer

   B — No — there is no update operation; a change invalidates O(n log n) precomputed windows, so you would rebuild from scratch. Use a segment tree — Static-versus-mutable is the whole decision in this phase: sparse table (static, O(1)), segment tree (mutable, O(log n)), Fenwick (mutable + invertible, less code).

5. How should `j = floor(log2(length))` be computed?

   A math.log2 per query B Precompute a log table with log[i] = log[i // 2] + 1 in one O(n) pass — it is faster and avoids floating-point edge cases at exact powers of two C Repeated division inside the query D int.bit_length() minus one is wrong here
   pch.quizShowAnswer

   B — Precompute a log table with log[i] = log[i // 2] + 1 in one O(n) pass — it is faster and avoids floating-point edge cases at exact powers of two — `(length).bit_length() - 1` also works and is exact. The point is to avoid float log in a hot query path.

6. You need the minimum of every sliding window of fixed width k. Sparse table?

   A Yes, one O(1) query per position B It works, but a monotonic deque gives all of them in O(n) total with O(k) space and no preprocessing — sparse tables are for arbitrary ranges, not sliding ones C No, that problem is unsolvable in O(n) D Yes, and it is asymptotically better
   pch.quizShowAnswer

   B — It works, but a monotonic deque gives all of them in O(n) total with O(k) space and no preprocessing — sparse tables are for arbitrary ranges, not sliding ones — O(n log n) preprocessing plus n queries versus a single O(n) pass. Matching the structure to how the ranges are shaped — arbitrary versus sliding — is the judgement being tested.

Recall card

• Cue — static array, many range min / max / gcd queries. No updates anywhere in the problem.
• Build — st[j][i] = answer for the window of length $2^j$ starting at i; st[j][i] = op(st[j-1][i], st[j-1][i + 2^(j-1)]). $O(n \log n)$ time and memory.
• Query [l, r] — j = floor(log2(r - l + 1)), then op(st[j][l], st[j][r - 2^j + 1]). Two lookups, no loop, $O(1)$.
• The windows overlap and that is fine — only because the operation is idempotent. This is the whole precondition.
• Not for sums — the overlap double-counts; prefix sums are $O(1)$ anyway.
• No updates — any change means a full rebuild. Mutable → segment tree.
• Precompute logs with log[i] = log[i//2] + 1, or use bit_length() - 1.
• Unlocks $O(1)$ LCA via Euler tour + RMQ over the depth array.

Recap

• A sparse table precomputes the answer for every range whose length is a power of two: $O(n \log n)$ rows and space, built once.
• Any query [l, r] is covered by two overlapping power-of-two windows, answered in $O(1)$ — the overlap only stays correct because min/max/gcd are idempotent.
• It cannot support updates — reach for a segment tree or Fenwick tree the moment the array changes.
• The same RMQ machinery, run over an Euler tour’s depth array, answers LCA queries in $O(1)$ too.

Next: Number Theory for Competitive Programming — modular arithmetic, fast exponentiation, sieves, and the combinatorics-mod-p toolkit that shows up in nearly every CP contest.