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.

Function Contracts

build_sparse_min(values) expects a fixed non-empty list of comparable values and returns a table of range minimums for power-of-two lengths.

query_min(table, left, right) expects valid inclusive query indexes and returns the minimum value in that range. It assumes the array has not changed since 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.

Query Idea

For a range minimum query, choose the largest power-of-two length that fits inside the query range. Two overlapping blocks of that length can cover the range:

def query_min(table, left, right):
    length = right - left + 1
    power = length.bit_length() - 1
    block = 1 << power
    return min(table[power][left], table[power][right - block + 1])

Overlap is safe for minimum because counting the same value twice does not change the minimum.

Why Static Data Matters

Sparse tables do not update efficiently. If one array value changes, many precomputed ranges can become invalid.

Complexity

Preprocessing is O(n log n) time and space. Range minimum or maximum query is O(1) with the overlapping-block method.

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.

Range sum does not use the same overlapping two-block query because overlapping would double-count values.

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.

Do not use it when frequent updates are part of the problem.

The Main Point

A sparse table is for many queries on fixed data. Its O(1) query trick works only for operations where overlapping blocks are safe, such as minimum.