All lessons
LESSON 37/53Searching and Sorting
Prefix Sums
GOALPrepare once, then answer any range-sum question instantly.
If you are asked "what do elements 3 to 7 add up to?" many times, looping each time is slow. Walk the array once, storing the total up to each point, and every later question becomes a single subtraction.
ON THIS PAGE
SHOW EXAMPLE IN
//THE EXAMPLE
main.cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {3, 1, 4, 1, 5, 9};
int n = (int)v.size();
vector<long long> p(n + 1, 0);
for (int i = 0; i < n; i++) {
p[i + 1] = p[i] + v[i];
}
// sum of v[1..3] = 1 + 4 + 1
cout << p[4] - p[1] << endl;
// sum of v[0..5] = everything
cout << p[6] - p[0] << endl;
return 0;
}> what you see
6 23
//LINE BY LINE
Watch it run
The original array: v = {3, 1, 4, 1, 5, 9}.
When it is worth building
Building the table costs one O(n) pass. For a single question a plain loop is cheaper. The gain arrives when there are MANY questions.
| Queries | With a loop | With prefix sums |
|---|---|---|
| 1 | n | n |
| 1 000 | 1 000 × n | n + 1 000 |
| 100 000 | 100 000 × n | n + 100 000 |
Prefix sums on a grid
The same idea works on a grid. A rectangle's total comes from four values — with the doubly-subtracted corner added back.
// build
p[r][c] = g[r][c] + p[r-1][c] + p[r][c-1] - p[r-1][c-1];
// sum of the rectangle (r1,c1) to (r2,c2)
total = p[r2][c2] - p[r1-1][c2] - p[r2][c1-1] + p[r1-1][c1-1];That last + is not a mistake. The top-left region was subtracted twice, so it is added back once.