Prefix sums
The sum of any range in after one pass. And the reverse: many range additions with a difference array.
When
The array does not change and many queries "sum from to " arrive. With , is too slow and is comfortable.
The idea
Set and . Then
The shift by one, with of length , removes the special case .
In two dimensions the same works by inclusion–exclusion: the rectangle is the big rectangle from the origin, minus two strips, plus the corner that was subtracted twice.
Difference array. This is the inverse operation. To add to all of , write and . At the end, the prefix sums of give the array.
The move that unlocks problems
"How many subarrays have sum ?" A subarray has sum if and only if . Go through in order and count in a map how many times you have already seen . The same with remainders solves "sum divisible by ".
Pitfalls
- The sums overflow
int: . Alwayslong long. - In
Subarray Divisibility, C++%gives a negative remainder for a negative number; fix it with((x % n) + n) % n.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Prefix sums and difference array.
// pref[i] = a[0] + ... + a[i-1], so the sum of a[l..r] is pref[r + 1] - pref[l].
vector<ll> buildPrefix(const vector<ll>& a) {
int n = a.size();
vector<ll> pref(n + 1, 0);
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + a[i];
}
return pref;
}
// Sum of a[l..r], both ends included, 0-indexed.
ll rangeSum(const vector<ll>& pref, int l, int r) {
return pref[r + 1] - pref[l];
}
// 2D: pref2[i][j] = sum of the rectangle with corners (0, 0) and (i - 1, j - 1).
vector<vector<ll>> buildPrefix2D(const vector<vector<ll>>& a) {
int n = a.size();
int m = 0;
if (n > 0) {
m = a[0].size();
}
vector<vector<ll>> pref(n + 1, vector<ll>(m + 1, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
pref[i + 1][j + 1] = a[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j];
}
}
return pref;
}
// Sum of the rectangle rows r1..r2, columns c1..c2 (inclusive).
ll rectSum(const vector<vector<ll>>& pref, int r1, int c1, int r2, int c2) {
return pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1];
}
// Difference array: many "add v to a[l..r]" updates, then one pass to read the result.
struct DiffArray {
vector<ll> d;
DiffArray(int n) : d(n + 1, 0) {}
void addRange(int l, int r, ll v) {
d[l] += v;
d[r + 1] -= v;
}
vector<ll> result() {
int n = (int)d.size() - 1;
vector<ll> a(n, 0);
ll running = 0;
for (int i = 0; i < n; i++) {
running += d[i];
a[i] = running;
}
return a;
}
};
Tested on 2,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Static Range Sum Queries · Range Queries
- Forest Queries · Range Queries
- Subarray Sums II · Sorting and Searching
- Subarray Divisibility · Sorting and Searching
More in the USACO Guide
- Introduction to Prefix Sums · usaco.guide/silver/prefix-sums
- More on Prefix Sums · usaco.guide/silver/more-prefix-sums
In English, with more problems per level.