Sparse Table (Range Minimum Query)

A sparse table answers range-minimum (or range-maximum, GCD, OR — any idempotent operation) queries on a fixed array in O(1) after an O(n log n) precomputation. The trick is to precompute the answer for every block whose length is a power of two, then cover any query range with just two overlapping such blocks.

For arr = [5, 2, 4, 7, 6, 3, 1, 8], the minimum of arr[2..6] is 1. We find it with two reads, no scan over the five elements.

Intuition

The minimum of a range does not change if you count some elements twice. That is the key property — min is idempotent, so min(a, a) = a. So instead of needing blocks that tile a range exactly, we can let two blocks overlap and still get the right answer.

Every range of length len can be covered by two blocks of length 2^k where 2^k is the largest power of two that is at most len: one block anchored at the left end l, one anchored so it ends at the right end r. Because 2^k > len / 2, those two blocks overlap in the middle and leave no gap. Precomputing the minimum of every power-of-two block lets us snap any query onto two of them instantly.

Walk through it

Step through the animation on the right. The top row is arr. Below it are the rows for j = 0, 1, 2.

Row j = 0 is just the array — each length-1 block is a single element. To build row j = 1, each cell combines two adjacent length-1 blocks: table[1][0] = min(arr[0], arr[1]) = min(5, 2) = 2, and so on across the row. Row j = 2 then stitches two length-2 blocks that sit two apart: table[2][0] = min(table[1][0], table[1][2]) = min(2, 4) = 2. Notice each higher row is shorter, because a longer block cannot start as far to the right.

Now the query min(arr[2..6]). The span is 5, so k = floor(log2(5)) = 2 and the block length is 4. We take the length-4 block starting at l = 2 (table[2][2] = 3) and the length-4 block ending at r = 6, which starts at r - 4 + 1 = 3 (table[2][3] = 1). They overlap on indices 3..5, but that is fine for min. The answer is min(3, 1) = 1.

The code, line by line

def build_sparse(arr):
    n = len(arr)
    table = [arr[:]]            # table[0][i] = arr[i]
    j = 1
    while (1 << j) <= n:
        prev, span = table[j - 1], 1 << (j - 1)
        table.append([min(prev[i], prev[i + span])
                      for i in range(n - (1 << j) + 1)])
        j += 1
    return table
 
def query(table, l, r):
    k = (r - l + 1).bit_length() - 1   # floor(log2(len))
    return min(table[k][l], table[k][r - (1 << k) + 1])

• table[0] is a copy of arr: the length-1 blocks are the elements themselves.
• The while doubles the block length each pass; span = 2^(j-1) is how far apart the two half-blocks sit.
• Lines 7–8 are the heart of the build: each new cell is the min of two previously computed half-blocks, and the comprehension only runs while a full 2^j block still fits (i + 2^j <= n).
• k = (r - l + 1).bit_length() - 1 is a fast integer floor(log2(len)).
• Line 14 combines the left-anchored block table[k][l] and the right-anchored block table[k][r - 2^k + 1]; their overlap is harmless because min is idempotent.

Complexity

There are about log n rows, and each cell is computed from two earlier cells in constant time, so the build is O(n log n). Every query then does a single bit_length, two array lookups, and one min — independent of the range size.

When to use / pitfalls

Practice