Algorithms / Prefix Sums
Least You Need to Know: Prefix Sums, Range Aggregates, and Subtracting History
Prefix sums precompute cumulative totals so a range sum becomes **one subtraction of two histories**. This is one of the highest-leverage preprocessing tricks in algorithmic problem solving.
The least you need to know
- A prefix sum stores the aggregate of the first part of an array.
- Range sum on `[l, r]` becomes `prefix[r] - prefix[l-1]` with 1-based indexing.
- Building prefixes costs linear time and space.
- Prefix ideas extend beyond sums to counts and other additive quantities.
- Prefix preprocessing is best for many queries on mostly static data.
Key notation
pref[i]
sum of elements up to index i
range(l, r)
aggregate over a contiguous interval
pref[r] - pref[l-1]
range-sum query by subtraction
Tiny worked example
- For array `[2, 5, 1, 4]`, the prefix sums are `[2, 7, 8, 12]`.
- The range sum from index `2` to `4` is `12 - 2 = 10`.
- Instead of re-adding the interval each time, reuse the cumulative totals.
- That is the main speedup provided by prefix sums.
Common mistakes
- Off-by-one mistakes are common around whether `pref[0]` is defined as zero.
- Prefix sums help most when the array is static or updates are rare.
- The trick requires an additive-like combine operation for simple subtraction.
How to recognize this kind of problem
- There are many interval-sum or interval-count queries on a static array.
- The problem asks for cumulative totals from the beginning up to each position.
- A direct re-scan of every query would be too slow.
Next recommended lesson
Continue through this topic with Least You Need to Know: Priority Queues, Scheduling, and Lazy Updates.
Least You Need to Know: Priority Queues, Scheduling, and Lazy UpdatesRelated lessons
Keep going with nearby lessons in the same topic.