When the array never changes
For range minimum queries on a static array, a sparse table is hard to beat. It precomputes answers for every range whose length is a power of two, then answers any query in constant time. The catch is that it does not support updates.
Building the table
You fill a table where one entry holds the minimum of the slice starting at a position and spanning a power of two length.
- Length one ranges are just the array elements.
- A range of double length is the minimum of two half length ranges that you already computed.
Because each longer range reuses two shorter ones, the whole table fills in a clean doubling pass.
Answering in constant time
For minimum, ranges may overlap without changing the answer, since taking the minimum twice over the same element is harmless. So to query any slice, pick the largest power of two that fits, then combine the range starting at the left with the range ending at the right. These two ranges cover the slice, possibly overlapping in the middle, and their minimum is the answer.
Why idempotence matters
This overlap trick only works for idempotent operations like minimum, maximum, or bitwise and. For sums, double counting the overlap would be wrong, so sums need a different structure.
Key idea
A sparse table precomputes power of two ranges so an idempotent query like minimum is answered in constant time by overlapping two covering ranges.