Sparse Tables and Range Queries

Given a fixed array — say, a day's minute bars of price — you often need to repeatedly answer "what was the minimum price between minute $i$ and minute $j$?" for many different ranges. A naive scan over each query range takes time proportional to the range length every time; if you're firing thousands of such queries, that adds up fast.

A sparse table precomputes, once, the minimum (or maximum) over every range whose length is a power of two, starting at every index. Table entry $\mathrm{sparse}[k][i]$ stores the minimum of the $2^k$ elements starting at index $i$, built up from smaller powers: $\mathrm{sparse}[k][i] = \min(\mathrm{sparse}[k-1][i],\ \mathrm{sparse}[k-1][i + 2^{k-1}])$. This precomputation takes $O(n \log n)$ time and space. Answering any range-minimum query afterward takes $O(1)$: pick the largest power of two, $2^k$, that fits inside the query range, and take the min of the two (possibly overlapping) precomputed blocks of that size covering the range — since min is idempotent, overlapping is harmless.

The catch is that this only works for static data and an idempotent operation like min, max, or gcd; it does not support updates after the table is built, and it doesn't work for sum (which double-counts the overlap). For that use case a segment tree, which supports updates, is the right tool instead.