If we have to compute the sum of a part of an array many times, we do not add everything up again each time: we compute the sums of all initial parts of the array once (the prefix sums), and then we get the sum of any part with one subtraction, in O(1) time.
Before you start: prior knowledge you need – arrays, matrices. How to learn: retype and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
Prefix sums
For an array a[1..n] we define p[0] = 0 and p[i] = a[1] + a[2] + … + a[i]. It is computed in one pass: p[i] = p[i − 1] + a[i]. The sum of the part from l to r is then
a[l] + … + a[r] = p[r] − p[l − 1]
i
0
1
2
3
4
5
6
a[i]
3
1
4
1
5
9
p[i]
0
3
4
8
9
14
23
For example, the sum a[2..5] = 1 + 4 + 1 + 5 = 11 = p[5] − p[1] = 14 − 3.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> p(n + 1, 0); // p[0] = 0
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
p[i] = p[i - 1] + x; // the sum of the first i elements
}
while (q--) {
int l, r;
cin >> l >> r; // positions start from 1
cout << p[r] - p[l - 1] << "\n"; // the sum a[l..r] in O(1)
}
return 0;
}
For the array from the table and the queries 2 5 and 1 6 the program prints 11 and 23.
The preparation takes O(n), and every query O(1) – O(n + q) in total instead of O(n · q). Indexing from 1 and p[0] = 0 remove the special case for l = 1.
The difference array: adding on an interval
The reverse problem: many times we have to add the value v to all elements from l to r, and the array is printed only at the end. Instead of changing all the elements, we write d[l] += v and d[r + 1] −= v into a helper array d. At the end, the prefix sums of the array d give how much was added to every element.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<long long> a(n + 2, 0), d(n + 2, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
while (q--) {
int l, r;
long long v;
cin >> l >> r >> v;
d[l] += v; // adding starts at l
d[r + 1] -= v; // and stops after r
}
long long added = 0;
for (int i = 1; i <= n; i++) {
added += d[i]; // the prefix sum of the difference array
cout << a[i] + added << " ";
}
cout << endl;
return 0;
}
For the input 5 2 / 1 1 1 1 1 / 1 3 2 / 2 5 10 the program prints 3 13 13 11 11.
Prefix sums in a matrix
For a matrix a[1..n][1..m] let p[i][j] be the sum of the rectangle from (1, 1) to (i, j):
(we added the upper and the left part, and their common part was counted twice, so we subtract it). The sum of the rectangle from (x1, y1) to (x2, y2):
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<long long>> p(n + 1, vector<long long>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
long long x;
cin >> x;
p[i][j] = x + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
}
while (q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1] << "\n";
}
return 0;
}
For the 3×3 matrix 1 2 3 / 4 5 6 / 7 8 9 and the query 2 2 3 3 the program prints 28 (5 + 6 + 8 + 9).
Practice tasks
Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.
TASK 01Difficulty: harder
Parts with a sum of exactly K
We are given an array of n integers (they may also be negative, 1 ≤ n ≤ 2·105) and a number K. How many contiguous parts of the array have a sum of exactly K?
Example 1
Input
5 3
1 2 1 -1 3
Output
5
Example 2
Input
3 0
0 0 0
Output
6
Hint
The sum of the part a[l..r] is p[r] − p[l − 1]. It is equal to K when p[l − 1] = p[r] − K. Go through the array and in a map(SR) remember how many times each prefix sum has appeared so far (at the beginning p[0] = 0 once). For every r add to the answer the number of earlier prefix sums equal to p[r] − K.
Solution (C++)
#include <iostream>
#include <map>
using namespace std;
int main() {
int n;
long long K;
cin >> n >> K;
map<long long, long long> count; // how many times each prefix sum has appeared
count[0] = 1; // the empty prefix p[0] = 0
long long p = 0, answer = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
p += x; // p = the sum of the first i+1 elements
if (count.count(p - K)) answer += count[p - K];
count[p]++;
}
cout << answer << endl;
return 0;
}
TASK 02Difficulty: easy
The best k days in a row
We are given the earnings for n days and a number k (1 ≤ k ≤ n ≤ 106). Print the largest total earnings for k consecutive days.
Example
Input
7 3
2 -1 4 5 -3 6 1
Output
8
Hint
With prefix sums, the sum of the days i − k + 1 .. i is p[i] − p[i − k]. Check all i from k to n.
Solution (C++)
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> p(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
p[i] = p[i - 1] + x;
}
long long best = p[k];
for (int i = k + 1; i <= n; i++) best = max(best, p[i] - p[i - k]);
cout << best << endl;
return 0;
}
Common mistakes and tips
Store prefix sums in long long – the sum of 105 numbers up to 109 goes beyond the range of int.
The sum a[l..r] is p[r] − p[l − 1], not p[r] − p[l].
The difference array must also have room for d[r + 1], i.e. a size of at least n + 2.
Prefix sums do not help if the array changes between queries – then a Fenwick tree(SR) is used.
Check your knowledge
Open the quiz
Prefix sums
1. How is the sum a[l..r] computed with prefix sums?
2. How long does one sum query take after the preparation?
3. What is the difference array used for?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.