CONCEPT · Pupil
Prefix sums
also cumulative sum · range sum
Precompute running totals so any contiguous sum is a subtraction. Works for any invertible combine: +, XOR, occurrence counts.
Intuition
sum[l..r] is 'everything up to r' minus 'everything before l'.
When to reach for it
- Many range-sum queries on a static array
- Counting how many times a property holds in a segment
- 2-D rectangle sums
Usual pits
- int overflow in C++
- Wrong identity at l = 0
- Using prefixes for min/max (not invertible)