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.