Sparse Table - Querying

To query min(l, r), compute $k = \lfloor \log_2(r - l + 1) \rfloor$. Then the answer is min(st[l][k], st[r - 2^k + 1][k]). This works because $2^k$ is the largest power of $2$ that fits in the range. The two ranges $[l, l + 2^k)$ and $[r - 2^k + 1, r + 1)$ overlap, but that is fine for min queries: min(a, b, c) = min(min(a, b), min(b, c)) even if b appears twice.

The overlapping ranges trick is specific to idempotent operations like min and max. It does not work for sum or count. Time: $O(1)$ per query because you only compute $k$, then look up two precomputed values and take their minimum. No loops needed.