Sparse Table (RMQ) Builder

Paste a list of integers and the Sparse Table Builder constructs the full 2D precomputation table that makes range-minimum queries answerable in O(1) time. The table has ⌊log₂ n⌋ + 1 levels; level k stores the minimum of every window of length 2^k starting at each index. Once that table exists, any query over a[l..r] resolves by reading two cells, one anchored at l and one ending at r, and returning the smaller of the two because the windows overlap and a minimum is idempotent.

RMQ appears throughout competitive programming wherever you need the cheapest or most powerful element in a moving window: lowest common ancestor on a tree (after Euler-tour flattening), static range queries on a frequency table, the denominator in a sliding-window ratio problem, and anywhere a Segment Tree would work but its O(log n) query is a bottleneck. Sparse Table trades update capability for raw query speed. The structure is read-only after construction, which makes it the right call when the array is fixed and queries are dense.

Worked Example: Nine Values, One Table

The lead sample is 3 6 2 1 8 4 7 5 9, nine elements. Level 0 is the array itself. Level 1 stores window-of-2 minima: min(3,6)=3, min(6,2)=2, min(2,1)=1, and so on. Level 2 stores window-of-4 minima: min(3,6,2,1)=1 at index 0, min(6,2,1,8)=1 at index 1, etc. A query over [1,4] (values 6 2 1 8) uses k=2 (the largest power of 2 that fits 4 elements): sp[2][1] = min(6,2,1,8) = 1. Change the query to [0,2] and the tool returns 2, the minimum of 3 6 2.

How the Algorithm Builds and Queries

Building the table takes O(n log n) time and space. Querying any range [l, r] takes O(1): compute k = ⌊log₂(r − l + 1)⌋, then return min(sp[k][l], sp[k][r − 2^k + 1]). The overlapping windows are valid because minimum is idempotent: counting an element twice does not change the result. Arrays up to 16 elements are accepted here; the generated C++ template scales to MAXN = 100001 and uses GCC's built-in __lg(x) for the floor-log₂ computation, which is a single instruction on x86.

When Not to Use a Sparse Table

• Point updates invalidate the table. If the array changes after construction, the entire table must be rebuilt in O(n log n). Use a Segment Tree instead when updates and queries are interleaved; its O(log n) query costs more per call but tolerates modifications without a full rebuild.
• Non-idempotent operations require a different structure.Sum and XOR are not idempotent (summing an element twice changes the result), so the overlapping-window trick is invalid. A Fenwick Tree or Segment Tree handles sum RMQ correctly in O(log n).
• Very large n needs care with LOG sizing.The generated template declares LOG = ⌊log₂ n⌋ + 1 at compile time. If you resize MAXN without updating LOG, level k = LOG will silently read out of bounds. Always derive both constants from the same value.