The setting
Sometimes an array never changes, and you only need to answer many range minimum or maximum queries. A sparse table trades a precomputation pass for queries that finish in constant time afterward.
Precomputing power of two blocks
Build a table where one entry holds the answer for the block starting at a given index whose length is a fixed power of two. You fill it by doubling: a block of length two combines two adjacent blocks of length one, a block of length four combines two blocks of length two, and so on.
Answering a query with two blocks
For an idempotent operation such as minimum or maximum, overlapping does not change the answer. So any query range can be covered by two precomputed blocks:
- Take the largest power of two block that fits, anchored at the left end.
- Take another such block anchored at the right end.
- Combine the two results, accepting that they may overlap in the middle.
Because overlap is harmless for minimum and maximum, the answer is exact. Operations like sum are not idempotent, so they need a different structure.
Key idea
Precompute answers for power of two blocks, then cover any range with two overlapping blocks when the operation is idempotent.