Sparse tables: precompute immutable range minima

Last updated: 5 Oct 20269 min read

tutorial

A sparse table stores the minimum for every power-of-two block starting at each valid position. For a nonempty half-open range [left, right), two blocks of the largest fitting power cover the range, possibly overlapping. Minimum is idempotent, so overlapping elements do not affect the result. Build time and space are O(n log n), while each minimum query is O(1). This two-block method does not work unchanged for sums because overlapping elements would be counted twice. The source array must remain immutable or the precomputed blocks become stale.

Operational case

A depot freezes six daily delay counts: 47, 31, 26, 58, 19, and 42. Its audit asks for the minimum over days [1, 5), which is 19. The query selects blocks covering indices 1 through 4; any overlap is harmless for minimum. If a late correction changes day 4, the table belongs to the old audit revision and cannot answer the new one. The immutable snapshot is a product decision as well as an algorithmic assumption. Use a segment tree if mixed point changes and range queries dominate.

Working Python program

daily_delay = [47, 31, 26, 58, 19, 42]
minimum_blocks = [daily_delay[:]]
block_width = 2
while block_width <= len(daily_delay):
    half = block_width // 2
    previous = minimum_blocks[-1]
    minimum_blocks.append([min(previous[start], previous[start + half]) for start in range(len(daily_delay) - block_width + 1)])
    block_width *= 2

def range_minimum(left, right):
    length = right - left
    level = length.bit_length() - 1
    width = 1 << level
    return min(minimum_blocks[level][left], minimum_blocks[level][right - width])

print(range_minimum(1, 5))
print(range_minimum(0, 3))

Output

19
26

Time, space, and tradeoff

The build creates O(log n) levels, each with at most n values, so its time and storage are O(n log n). A query performs constant arithmetic and two table reads. Validate 0 <= left < right <= n; an empty range has no minimum without an application-defined identity. The sample uses Python integers and nested lists for clarity; a compact numeric array lowers storage overhead at large n. Rebuilding after every edit is costly, which is why this representation belongs to a frozen revision rather than a live counter.

Common Mistakes

Do not apply the overlapping-block shortcut to a non-idempotent sum.
Do not query an empty minimum range without a stated result.
Do not reuse a table after its source snapshot changes.

Connected lessons

Disjoint sparse tables: immutable sums with constant-time queries extends this range-query decision.

Cartesian trees: preserve sequence order under a heap minimum adds a distinct structure contract to compare.

data structures

range-query-structures