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 ll and rr?” 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 minmin, maxmax, or gcdgcd), 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][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.

Building the table: powers of two

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

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

Row 00 is just the array itself (ranges of length $2^0 = 1$ ). Row jj is built from row j - 1j - 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

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][l, r] of length lenlen is covered by two windows of length $2^j$ where $j = \lfloor \log_2(\text{len}) \rfloor$ : one starting at ll, one ending at rr. 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)min(min(x, x), y) == min(x, y), so double-counting the overlapping middle changes nothing. The same trick would silently break for sumsum, which double-counts real values.

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

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 jj is looked up from a precomputed loglog table in O(1)O(1) — recomputing math.log2math.log2 on every query would still be O(1)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 minmin for maxmax or math.gcdmath.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

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

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

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**51 <= len(nums) <= 10**5, 1 <= nums[i] <= 10**61 <= nums[i] <= 10**6.

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

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)a & b <= min(a, b), because AND only ever clears bits. So every subarray’s AND is at most max(nums)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][1,2,3,3,2,2] has two 3s and they happen to be adjacent; if the input were [3,1,3][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][1,2,3,4].
All equal gives the whole length.
nums[i] >= 1nums[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 kk 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]arr[l..r]. Return the minimum possible value of abs(func(arr, l, r) - target)abs(func(arr, l, r) - target) over all subarrays.

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

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

Editorial · approach, complexity, follow-ups

The technique — maintain the set of results of all subarrays ending at ii — 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 ii 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 nn.

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

{n} | ...{n} | ... is what starts the length-1 subarray at ii. 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)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)abs(arr[0] - target), and the initialisation handles it before the loop.
[1000000]*3[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 rr. 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]nums[i..j] is min(nums[i..j]) * (j - i + 1)min(nums[i..j]) * (j - i + 1). A subarray is good if i <= k <= ji <= k <= j. Return the maximum score of a good subarray.

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

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

Editorial · approach, complexity, follow-ups

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

Why expanding toward the taller neighbour is safe. Suppose the optimal window has width ww. The greedy also produces some window of width ww, 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 ww has a minimum at least as large as any other width-ww window containing kk — and since the score is minimum × widthminimum × width, at equal width the higher minimum wins. So the greedy’s width-ww 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 floorfloor with both ends, min(floor, nums[left], nums[right])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 == 0left == 0 before comparing avoids indexing at -1-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]nums[0] and the loop never runs.
k = 0k = 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 kk. 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 kk?” — that is Largest Rectangle in Histogram, so monotonic stack. “Maximise min × lengthmin × length for exactly length ww?” — 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

#	Problem	Difficulty	The twist
—	Static Range Minimum Query (classic)	—	The direct competitive-programming staple (seen constantly on Codeforces and SPOJ as `RMQSQRMQSQ`): exactly the sparse table above, with no updates in the problem
239	Sliding Window Maximum	Hard	(Hard) — a different tool for a different shape of problem: the window slides by one each step instead of jumping to arbitrary `[l, r][l, r]` pairs, so a monotonic deque wins here over a sparse table
303	Range Sum Query - Immutable	Easy	(Easy) — the non-idempotent analog: since `sumsum` 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

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][l, r] is covered by two overlapping power-of-two windows, answered in $O(1)$ — the overlap only stays correct because minmin/maxmax/gcdgcd 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Sparse Tables and Range Minimum Query

What you’ll learn

Building the table: powers of two

Querying in O(1): two overlapping windows

Complexity

Practice — real LeetCode problems

LC 2419 — Longest Subarray With Maximum Bitwise AND · Medium

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

LC 1793 — Maximum Score of a Good Subarray · Hard

LeetCode problem set

Recap

Was this page helpful?