foundation
Prefix sums
Precompute cumulative totals or counts so range queries become constant-time differences.
Prefix sums store cumulative totals so a range sum becomes the difference between two checkpoints. The same idea works for counts, balances, XOR, and two-dimensional grids. It is especially useful when many range queries would otherwise repeat the same scan.
On interviews: Interviewers expect clear indexing, an initial zero prefix, and a comparison between preprocessing cost and query savings.
Common pitfalls: Off-by-one mistakes are common. Prefix sums help immutable query workloads but are less convenient when many point updates occur; then Fenwick or segment trees may fit better.
Checklist: