Prefix sums are one of the first techniques that make a beginner's solutions dramatically faster. The idea takes a minute to learn, and it turns up everywhere: range sums, counting problems, 2D grids, and as a building block inside harder algorithms.
The problem
You have an array of n numbers and q questions. Each question gives two positions l and r and asks for al + al+1 + … + ar. Both n and q can be 2 × 105.
Looping from l to r for each question costs up to n steps per question, so 4 × 1010 steps in the worst case. That is far too slow. We want each answer in constant time.
The idea
Build a second array where each entry stores the total of everything up to that point:
pre[0] = 0
pre[i] = a[1] + a[2] + ... + a[i] = pre[i - 1] + a[i]Building it takes one pass. Now notice that the sum from l to r is “everything up to r” minus “everything before l”:
sum(l, r) = pre[r] − pre[l − 1]
That is one subtraction per question, no matter how wide the range is.
Worked example
Take the array 3 1 4 1 5 9 (positions 1 to 6).
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| a[i] | – | 3 | 1 | 4 | 1 | 5 | 9 |
| pre[i] | 0 | 3 | 4 | 8 | 9 | 14 | 23 |
The sum from position 3 to 5 is pre[5] − pre[2] = 14 − 4 = 10, and indeed 4 + 1 + 5 = 10. The sum of the whole array is pre[6] − pre[0] = 23.
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
// pre[i] = a[1] + a[2] + ... + a[i], with pre[0] = 0
vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
pre[i] = pre[i - 1] + x;
}
while (q--) {
int l, r;
cin >> l >> r;
cout << pre[r] - pre[l - 1] << '\n';
}
return 0;
}The input format matches CSES 1646 – Static Range Sum Queries: n and q, then the array, then q lines with l and r.
Complexity
O(n) to build the prefix array and O(1) per query, so O(n + q) in total, with O(n) extra memory.
Why the extra zero matters
Starting the array with pre[0] = 0 and using 1-based positions means the formula works even when l = 1, because pre[l − 1] = pre[0] = 0. If you use 0-based indexing without that extra slot, you need a special case for queries starting at the first element, and special cases are where bugs live.
Common mistakes
- Overflow. 2 × 105 values of up to 109 add up to 2 × 1014. Store prefix sums in
long longeven if the input fits inint. - Off by one. It is pre[r] − pre[l − 1], not pre[r] − pre[l]. The second version drops al.
- Slow input. With 2 × 105 queries, unbuffered
cincan be the bottleneck. The two lines at the top ofmainfix that.
Beyond sums
The same trick works for anything you can “undo”. Prefix XOR answers range XOR queries, because x XOR x = 0. Prefix counts answer questions like “how many even numbers are between l and r”: build an array that adds 1 for each position that satisfies the condition. In 2D, the sum of a rectangle can be found from four prefix values using inclusion–exclusion.
It does not work for minimum or maximum, because you cannot subtract a minimum. Those need other structures, such as a sparse table or a segment tree.
Practice problems
- CSES 1646 – Static Range Sum Queries: the exact problem above.
- Codeforces 313B – Ilya and Queries: a prefix count of positions where two neighbouring characters are equal.
- Codeforces 433B – Kuriyama Mirai's Stones: two prefix arrays, one on the original order and one after sorting.
If you have not yet read it, my post on how to read constraints starts from the same “range sum” example and explains why 2 × 105 queries rule out the simple loop.
