Sparse tables: range queries after preprocessing. Structure: st[i][j] = answer for range starting at with length . 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: query. Space: .