Chapter 13 of 30
Prefix Sums & Difference Arrays
Master prefix sums, 2D prefix sums, suffix sums, and difference arrays for efficient range queries and updates.
1D Prefix Sums2D Prefix SumsSuffix Sums & Suffix AggregatesDifference Arrays
Share:
Prefix Sums & Difference Arrays
Prefix sums let you answer range queries in O(1) after O(n) preprocessing. Difference arrays let you apply range updates in O(1). Together, they're the most-used technique for array manipulation.
1D Prefix Sums
Construction
hljs cpp
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + a[i];
}
Range Sum Query [l, r]
hljs cpp
long long rangeSum = prefix[r + 1] - prefix[l];
Example: Count Subarrays with Sum = k
hljs cpp
// Use prefix sums + hashmap
map<long long, int> count;
count[0] = 1;
long long prefix = 0;
int result = 0;
for (int i = 0; i < n; i++) {
prefix += a[i];
result += count[prefix - k];
count[prefix]++;
}
Prefix Sums with Modulo
hljs cpp
// Count subarrays where sum % k == 0
vector<int> modCount(k, 0);
modCount[0] = 1;
long long prefix = 0;
int result = 0;
for (int i = 0; i < n; i++) {
prefix = (prefix + a[i]) % k;
if (prefix < 0) prefix += k;
result += modCount[prefix];
modCount[prefix]++;
}
2D Prefix Sums
For sum queries on a 2D grid:
Construction
hljs cpp
vector<vector<long long>> prefix(n + 1, vector<long long>(m + 1, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
prefix[i + 1][j + 1] = a[i][j]
+ prefix[i][j + 1]
+ prefix[i + 1][j]
- prefix[i][j];
}
}
2D Range Sum Query
hljs cpp
// Sum of subgrid from (r1, c1) to (r2, c2) inclusive
long long sum = prefix[r2 + 1][c2 + 1]
- prefix[r1][c2 + 1]
- prefix[r2 + 1][c1]
+ prefix[r1][c1];
Inclusion-Exclusion Principle
The 2D formula works because we're adding/subtracting rectangles:
- Add the full rectangle from (0,0) to (r2,c2)
- Subtract the strip above the region
- Subtract the strip to the left
- Add back the overlap (subtracted twice)
Suffix Sums & Suffix Aggregates
Suffix sums are prefix sums computed from right to left:
hljs cpp
vector<long long> suffix(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
suffix[i] = suffix[i + 1] + a[i];
}
Maximum Subarray Sum (Kadane's Algorithm)
hljs cpp
long long maxSum = a[0], currentSum = a[0];
for (int i = 1; i < n; i++) {
currentSum = max((long long)a[i], currentSum + a[i]);
maxSum = max(maxSum, currentSum);
}
Difference Arrays
A difference array lets you apply range updates in O(1):
Range Update: Add v to all elements in [l, r]
hljs cpp
vector<int> diff(n + 1, 0);
// Apply update
diff[l] += v;
if (r + 1 < n) diff[r + 1] -= v;
// Reconstruct the actual array
vector<int> result(n);
result[0] = diff[0];
for (int i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
Multiple Range Updates
hljs cpp
// Apply k updates
for (int i = 0; i < k; i++) {
int l, r, v;
cin >> l >> r >> v;
diff[l] += v;
if (r + 1 < n) diff[r + 1] -= v;
}
// Reconstruct once
int current = 0;
for (int i = 0; i < n; i++) {
current += diff[i];
a[i] += current;
}
2D Difference Array
hljs cpp
// Update subgrid (r1,c1) to (r2,c2) by v
diff[r1][c1] += v;
diff[r1][c2 + 1] -= v;
diff[r2 + 1][c1] -= v;
diff[r2 + 1][c2 + 1] += v;
// Reconstruct using 2D prefix sums
Summary
- Prefix sums: O(1) range sum queries after O(n) preprocessing
- 2D prefix sums: O(1) subgrid sum queries using inclusion-exclusion
- Difference arrays: O(1) range updates, then O(n) to reconstruct
- Prefix sums + hashmap: powerful pattern for counting subarrays with specific properties
- Kadane's algorithm: O(n) maximum subarray sum using suffix reasoning
Prefer reading offline? Download the full book as a PDF.
Download Free Book