Sparse Table

You have an array of numbers and a flood of questions: "What is the minimum value between index 3 and index 11?" Answering each naively takes \(O(n)\). A segment tree answers each in \(O(\log n)\). But a sparse table answers each in \(O(1)\) — after paying a one-time \(O(n \log n)\) build cost.

The catch: sparse tables only work for idempotent operations — operations where overlapping intervals don't double-count. Minimum and maximum are idempotent: min(min(a,b), min(b,c)) = min(a,b,c). Sum is not — adding the same elements twice gives the wrong answer.

The key idea — power-of-2 intervals

A sparse table precomputes the answer for every interval whose length is a power of 2: length 1, 2, 4, 8, 16, ... For any query range [L, R], you can always cover it with exactly two overlapping power-of-2 intervals that together span the whole range. Because min is idempotent, the overlap doesn't matter.

Building the table

Let table[j][i] = the minimum of the 2^j elements starting at index i.

Base case (j=0): table[0][i] = arr[i] — intervals of length 1
Recurrence: table[j][i] = min(table[j-1][i], table[j-1][i + 2^(j-1)])

Each level doubles the interval length. You build \(\log_2(n)\) levels, each taking \(O(n)\) work — total \(O(n \log n)\).

Answering a query in \(O(1)\)

For a range query [L, R]:

Compute k = floor(\(\log_2(R - L + 1)\)) — the largest power of 2 that fits in the range
Return min(table[k][L], table[k][R - 2^k + 1])

These two intervals overlap but together cover [L, R] completely. Because min is idempotent, the overlap is harmless. Two table lookups — \(O(1)\) total.

When to use a sparse table

Static arrays that never change after build time
Massive number of range minimum/maximum queries
When \(O(1)\) per query matters more than supporting updates

If the array changes, use a segment tree or Fenwick tree instead — they support \(O(\log n)\) updates at the cost of \(O(\log n)\) queries.

Sparse Table: Build & RMQ

import math

def build(arr):
    n = len(arr)
    LOG = max(1, int(math.log2(n)) + 1)
    table = [[0]*n for _ in range(LOG)]
    table[0] = arr[:]
    for j in range(1, LOG):
        for i in range(n - (1 << j) + 1):
            table[j][i] = min(table[j-1][i], table[j-1][i + (1 << (j-1))])
    return table

def rmq(table, l, r):
    """Range Minimum Query on [l, r] — O(1)."""
    k = int(math.log2(r - l + 1))
    return min(table[k][l], table[k][r - (1 << k) + 1])

arr = [2, 4, 3, 1, 6, 7, 8, 9, 1, 7]
table = build(arr)
print(rmq(table, 0, 4))  # min(2,4,3,1,6) = 1
print(rmq(table, 3, 8))  # min(1,6,7,8,9,1) = 1
print(rmq(table, 1, 5))  # min(4,3,1,6,7) = 1

Output

1
1
1

Sparse Table: Range Maximum Query

import math

def build_max(arr):
    n = len(arr)
    LOG = max(1, int(math.log2(n)) + 1)
    table = [[0]*n for _ in range(LOG)]
    table[0] = arr[:]
    for j in range(1, LOG):
        for i in range(n - (1 << j) + 1):
            table[j][i] = max(table[j-1][i], table[j-1][i + (1 << (j-1))])
    return table

def rmq_max(table, l, r):
    k = int(math.log2(r - l + 1))
    return max(table[k][l], table[k][r - (1 << k) + 1])

arr = [3, 1, 4, 1, 5, 9, 2, 6]
table = build_max(arr)
print(rmq_max(table, 0, 4))  # max(3,1,4,1,5) = 5
print(rmq_max(table, 3, 7))  # max(1,5,9,2,6) = 9