Section Recap

Sparse tables: $O(1)$ range queries after $O(n \log n)$ preprocessing. Structure: st[i][j] = answer for range starting at $i$ with length $2^j$. Build: st[i][j] = combine(st[i][j-1], st[i + 2^{j-1}][j-1]) Query (idempotent): Overlap two power-of-2 ranges covering query range.

Limitation: Only works for idempotent operations (min, max, GCD).

Range sum needs different approach. Time: $O(1)$ query. Space: $O(n \log n)$.