Prefix Sum
Precompute running totals once in O(n), then answer any range-sum query with one subtraction in O(1).
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
A car odometer. To know how far you drove between Adama and Hawassa, you don’t add up every kilometre again. You subtract the odometer reading at Adama from the reading at Hawassa.
A prefix sum array is that odometer: p[i] = sum of the first i items.
p[0] = 0;
p[i + 1] = p[i] + a[i];
sum(a[l..r]) = p[r + 1] - p[l];Building it is O(n), once. After that, any range sum is O(1). That is the time/space trade-off from Chapter 2: spend O(n) memory to save repeated work.
Built on arrays and time/space trade-offs (Ch1–2). Not on the exam.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
After building, set pos = 1 and value = 4 to get sum(a[1..4]) from two cells.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <vector>
using namespace std;
vector<int> buildPrefix(const vector<int>& a) {
vector<int> p(a.size() + 1, 0); // p[i] = sum of first i items
for (int i = 0; i < (int)a.size(); i++) p[i + 1] = p[i] + a[i];
return p;
}
int rangeSum(const vector<int>& p, int l, int r) { // sum of a[l..r]
return p[r + 1] - p[l];
}
int main() {
vector<int> a = {3, 1, 4, 1, 5, 9, 2};
vector<int> p = buildPrefix(a);
cout << "prefix: ";
for (int x : p) cout << x << " ";
cout << "\n";
cout << "sum a[1..4] = " << rangeSum(p, 1, 4) << "\n";
cout << "sum a[0..6] = " << rangeSum(p, 0, 6) << "\n";
cout << "sum a[5..5] = " << rangeSum(p, 5, 5) << "\n";
}prefix: 0 3 4 8 9 14 23 25 sum a[1..4] = 11 sum a[0..6] = 25 sum a[5..5] = 9
05Complexity
| build | O(n) |
|---|---|
| each range query | O(1) |
| q queries without prefix sums | O(n·q) |
| Extra space | O(n) |
Using size n + 1 with p[0] = 0 removes the special case for ranges that start at index 0.
06Watch
Prefix Sum in 4 minutes
Why this one: The whole pattern in 4 minutes.
Subarray Sum Equals K: Prefix Sums
Why this one: NeetCode combines prefix sums with a hash map (Chapter 8) for Subarray Sum Equals K.
Original class slides (Python, by the course's lecture authors):Prefix Sum
07Exam lens
Likely questions
- Build the prefix array of a given array and compute a range sum.
- Why is
pone longer thana?
Common mistakes
- Writing
p[r] − p[l]. With the n + 1 layout it isp[r + 1] − p[l]. - Rebuilding the prefix array for every query.
08Quick check
09Practice
🟢 Trace by hand
a = 3 1 4 1 5 9 2. Build p and compute sum(a[1..4]), sum(a[0..6]) and sum(a[5..5]).
Show answer
p = 0 3 4 8 9 14 23 25
- a[1..4] = p[5] − p[1] = 14 − 3 = 11
- a[0..6] = p[7] − p[0] = 25
- a[5..5] = p[6] − p[5] = 9
🟡 Implement it
Find the pivot index where the sum of the left side equals the sum of the right side.
Hint
Total = p[n]. At index i: left = p[i], right = total − p[i + 1].
🔴 Solve problems
Hint
Build p in the constructor; sumRange is one subtraction.
Hint
Left sum vs total − left − a[i].
Hint
Count how many earlier prefix sums equal
current − k, using an unordered_map.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.