Sparse Table

A sparse table preprocesses a fixed array so certain range queries can be answered quickly.

It is most often used for range minimum or maximum queries on data that does not change.

Core Idea

The table stores answers for ranges whose lengths are powers of two. A query combines one or two precomputed ranges, depending on the operation.

For idempotent operations such as minimum and maximum, range queries can be answered in O(1) after O(n log n) preprocessing.

Python Example

import math
 
def build_sparse_min(values):
    table = [values[:]]
    length = 1
 
    while 2 * length <= len(values):
        previous = table[-1]
        row = []
        for i in range(len(values) - 2 * length + 1):
            row.append(min(previous[i], previous[i + length]))
        table.append(row)
        length *= 2
 
    return table

The rows store minimums for ranges of length 1, 2, 4, and so on.

Common Confusions

A sparse table is usually for static arrays. If the array changes often, a segment tree or Fenwick tree may fit better.

Not every operation can be queried with the same simple overlap trick. Minimum works because overlapping the two selected ranges does not change the result.

When To Use It

Use a sparse table for many queries on a fixed array, especially range minimum, range maximum, or other operations where overlapping precomputed ranges are valid.