Sparse tables: idempotent queries in O(1)

Prefix sums answer range sum in O(1) because sum has an inverse: sum(l, r) = P[r+1] − P[l], you subtract off the part you don't want. Range minimum has no inverse — there is no "un-min" operation. So the prefix trick dies, and you reach for a sparse table: O(1) range min/max/gcd on a static array, after an O(n log n) precompute.

The table stores the answer for every power-of-two block. sparse[k][i] is the op applied over the 2ᵏ elements starting at i. Each level is built from the one below by combining two half-blocks.

To answer min(l, r), let k = ⌊log₂(r − l + 1)⌋ and take the op of just two blocks of length 2ᵏ: one starting at l, one ending at r. They overlap in the middle — and that is allowed only because min is idempotent: min(x, x) = x, so double-covering the overlap costs nothing.

Concretely, on a = [5, 2, 4, 7, 6, 3, 1, 2], query min(1, 5): the length is 5, so k = 2 (blocks of 4). Block one is a[1..4] = {2,4,7,6} → min 2; block two is a[2..5] = {4,7,6,3} → min 3. The answer is min(2, 3) = 2, matching min{2,4,7,6,3} = 2. The two blocks overlapped on indices 2–4, and it did not matter.

That idempotence requirement is the catch: sparse tables work for min, max, gcd, bitwise and/or — operations where overlap is harmless. They do not work for sum, because the overlap would be counted twice. And the array must be static: there is no cheap update. When you need updates too, the next two lessons take over.