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.
Least you need to know
- A prefix sum stores the aggregate of the first part of an array.
- Range sum on
[l, r]becomesprefix[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
Worked example
- For array
[2, 5, 1, 4], the prefix sums are[2, 7, 8, 12]. - The range sum from index
2to4is12 - 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 it
- 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.