Power-of-2 Ranges

Sparse Table precomputes $\text{st}[i][j]$ = answer for range starting at index $i$ with length $2^j$.

st[i][0] = arr[i]           # length 1
st[i][1] = min(st[i][0], st[i+1][0])  # length 2
st[i][2] = min(st[i][1], st[i+2][1])  # length 4
...
st[i][j] = min(st[i][j-1], st[i + 2^(j-1)][j-1])

Each entry combines two half-size ranges:

• Range $[i, i + 2^j - 1]$ combines $[i, i + 2^{j-1} - 1]$ and $[i + 2^{j-1}, i + 2^j - 1]$

Total entries: $O(n \log n)$. Each computed in $O(1)$.

Preprocessing time: $O(n \log n)$.