Why This Matters
Prefix sums turn repeated range-sum queries into constant-time lookups after one linear preprocessing pass. They also solve subarray-sum counting problems that sliding window cannot handle when values may be negative.
The invariant is that prefix[i] stores the sum of elements before index i.
Prerequisite Check
Review Arrays and Hash tables. Prefix sums use arrays for cumulative totals and hash maps for "have I seen a previous prefix with this value?" questions.
Learning Objectives
By the end, you should be able to:
- Build a prefix array with a leading zero.
- Answer inclusive and half-open range sums correctly.
- Count subarrays with a target sum using previous prefix counts.
- Choose prefix sums over sliding window for signed values.
- Extend the idea to 2D prefix sums and Fenwick trees.
Core Idea
If prefix[i] is the sum of values[0:i], then the sum of values[left:right] is prefix[right] - prefix[left].
| Pattern | Invariant | Typical problem |
|---|---|---|
| Static range sum | prefix[i] = sum(values[:i]) | many range queries |
| Target subarray count | previous prefixes count needed differences | count subarrays summing to k |
| 2D prefix sum | rectangle sum from corner sums | image/grid queries |
| Difference array | prefix reconstructs point values | range updates offline |
Visual Model
values: [3, -1, 4, 2]
prefix: [0, 3, 2, 6, 8]
sum values[1:3] = prefix[3] - prefix[1] = 6 - 3 = 3
The leading zero makes empty prefixes and ranges starting at zero clean.
Non-Example or Failure Mode
Prefix sums are not enough for frequent online updates. If values change repeatedly and range queries must stay fast, use Fenwick trees or segment trees.
Worked Example
Count subarrays summing to 3 in [1, 2, 1, 2].
running prefix: 1, 3, 4, 6
need prefix - 3:
at 3, need 0 -> found one subarray [1,2]
at 4, need 1 -> found one subarray [2,1]
at 6, need 3 -> found one subarray [1,2]
LeetCode-Style Problem Patterns
| Pattern | Recognition signal | Move |
|---|---|---|
| Range sum query | many sum queries on static array | build prefix once |
| Subarray sum equals K | values may be negative | hash counts of previous prefixes |
| Product except self analogy | prefix/suffix accumulation | scan from both sides |
| 2D matrix sum | rectangle queries | 2D prefix inclusion-exclusion |
Common Mistakes
| Mistake | Correction |
|---|---|
| Omitting the leading zero. | Use prefix[0] = 0 so prefix[right] - prefix[left] works uniformly. |
| Mixing inclusive and half-open endpoints. | Pick one convention and name it. |
| Using sliding window with negative values. | Prefix sums handle signed values. |
| Updating values but keeping stale prefixes. | Rebuild or use an update-friendly structure. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What does prefix[i] store in the common convention? | Sum of elements before index i. |
| Example / non-example | Do prefix sums support fast arbitrary updates? | No; use Fenwick or segment trees for online updates. |
| Computation | How do you get sum(values[left:right])? | prefix[right] - prefix[left]. |
| Proof | Why does subtraction isolate a range? | Shared earlier terms cancel. |
| Transfer | Why do prefix counts solve signed subarray sums? | They look for any previous prefix difference, independent of monotonicity. |
Exercises
Beginner:
- Build prefix sums for
[2, 4, -1, 3]. - Answer three half-open range-sum queries.
- Explain why a leading zero helps.
Intermediate:
- Count subarrays that sum to
k. - Implement a 2D prefix sum for rectangle queries.
Challenge:
- Convert a batch of range increment operations into a difference array and reconstruct final values.
Diagram Recommendation
Type: cancellation diagram.
Caption: "Subtracting two prefixes cancels everything before the range."
Purpose: Make endpoint conventions and off-by-one choices visible.
Implementation Task
Implement static range sums and target subarray counts. Include negative values in the tests.
Run prefix-sum range and subarray counts
This cell checks half-open range sums and signed subarray-sum counting.
Output will appear here.
Next Topics
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- Princeton Algorithms, Analysis of Algorithms: https://algs4.cs.princeton.edu/14analysis/
- Python documentation, dictionary type: https://docs.python.org/3/library/stdtypes.html#mapping-types-dict