The Overlap Trick

To query range $[l, r]$:

$1.$ Find the largest power of 2 that fits: $k = \lfloor \log_2(r - l + 1) \rfloor$

$2.$ Take $\min$ of two overlapping ranges of length $2^k$:

• One starting at $l$: $\text{st}[l][k]$
• One ending at $r$: $\text{st}[r - 2^k + 1][k]$

def query(l, r):
    length = r - l + 1
    k = int(log2(length))
    return min(st[l][k], st[r - (1 << k) + 1][k])

These two ranges cover $[l, r]$ completely, possibly overlapping in the middle. Since $\min$ is idempotent, overlapping is fine.

Time: $O(1)$ per query (with precomputed $\log$ values).