"What is the sum of a[l..r]?", asked a hundred thousand times: adding up the range each time is O(n) per question, far too slow. Prefix sums answer each question in O(1).
The idea
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a = {3, 1, 4, 1, 5, 9};
int n = a.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
int queries[3][2] = {{0, 2}, {2, 5}, {4, 4}};
for (int k = 0; k < 3; k++) {
int l = queries[k][0], r = queries[k][1];
cout << "sum a[" << l << ".." << r << "] = " << pre[r + 1] - pre[l] << "\n";
}
return 0;
}Build pre with one extra cell: pre[0] = 0 and pre[i + 1] = pre[i] + a[i], so pre[i] is the sum of the first i numbers. Then the sum of a[l..r] is pre[r + 1] - pre[l]: everything up to r, minus everything before l. Watch pre fill in one pass.
Counting with prefix sums
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a = {2, 7, 4, 4, 9, 6};
int n = a.size();
vector<int> evens(n + 1, 0);
for (int i = 0; i < n; i++) evens[i + 1] = evens[i] + (a[i] % 2 == 0 ? 1 : 0);
cout << "evens in a[1..4]: " << evens[5] - evens[1] << "\n";
return 0;
}The same trick counts things: let pre[i] be how many of the first i numbers are even. Then any range's count is one subtraction.
It also works in two dimensions: p[i][j] holds the sum of the rectangle above and left of (i, j), and any rectangle's sum takes four lookups.
Off-by-one. The extra cell (pre has n + 1 cells) removes the special case for ranges that start at 0. Use long long for pre: the sums grow large.
Quick check
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.