Sparse Tables

If your data never changes and you need range minimum (or maximum) queries, a sparse table answers them in O(1) after O(n log n) preprocessing. No updates, but nothing is faster for static queries. This post breaks down what sparse tables are, how they work under the hood, and why they're the optimal choice for static range-min/max problems.

What is a sparse table?

A sparse table is a precomputed 2D table where table[k][i] stores the answer (min, max, GCD, etc.) for the range starting at index i with length 2^k.