AdvancedData Structures & Algorithms · Lesson 19 of 20 · Updated ·
Prefix Sums and Difference Arrays — Fast Range Queries and Updates
Many problems ask the same kind of question again and again: "what is the sum of the elements from index l to r?" Adding them up each time costs O(n) per question — too slow when there are 10⁵ questions. A prefix sum array answers every such question in O(1) after one O(n) pass. Its mirror image, the difference array, does the opposite: it applies "add v to every element from l to r" in O(1).
1. The prefix sum array
P[i] = the sum of the first i elements. So P[0] = 0, P[1] = a[0], P[2] = a[0] + a[1], and so on. P has one more cell than a.
Then the sum of a[l..r] (both ends included) is:
sum(l, r) = P[r + 1] − P[l]
def build_prefix(a):
P = [0]
for x in a:
P.append(P[-1] + x)
return P
a = [3, 1, 4, 1, 5, 9, 2]
P = build_prefix(a)
print(P)
def range_sum(l, r): # inclusive
return P[r + 1] - P[l]
print(range_sum(2, 5), range_sum(0, 6), range_sum(3, 3))
[0, 3, 4, 8, 9, 14, 23, 25]
19 25 1
The extra leading 0 removes every special case: a range that starts at index 0 is just P[r + 1] − P[0].
2. Prefix sums + hash map: count subarrays with sum k
Problem: count the subarrays whose sum is exactly k. The array may contain negative numbers, so the sliding window doesn't work.
Idea: a subarray a[l..r] has sum k exactly when P[r + 1] − P[l] = k, that is, when an earlier prefix sum equals current − k. Walk through the array keeping the running sum, and a hash map of how many times each prefix sum has appeared so far.
def count_subarrays(a, k):
seen = {0: 1} # the empty prefix has sum 0
total = count = 0
for x in a:
total += x
count += seen.get(total - k, 0)
seen[total] = seen.get(total, 0) + 1
return count
print(count_subarrays([1, 2, 3], 3))
print(count_subarrays([1, -1, 1, -1], 0))
2
4
For [1, 2, 3] and k = 3 the two subarrays are [1, 2] and [3]. This runs in O(n) time. The same trick solves "longest subarray with sum k" (store the first index of each prefix sum) and "subarray sum divisible by k" (store prefix sums mod k).
The Java version uses a HashMap<Long, Integer>:
import java.util.HashMap;
public class Main {
static int countSubarrays(int[] a, int k) {
HashMap<Long, Integer> seen = new HashMap<>();
seen.put(0L, 1);
long total = 0;
int count = 0;
for (int x : a) {
total += x;
count += seen.getOrDefault(total - k, 0);
seen.merge(total, 1, Integer::sum);
}
return count;
}
public static void main(String[] args) {
System.out.println(countSubarrays(new int[]{1, 2, 3}, 3));
System.out.println(countSubarrays(new int[]{1, -1, 1, -1}, 0));
}
}
2
4
Use long for the running sum: 10⁵ values of 10⁹ add up to 10¹⁴, far beyond int.
3. 2D prefix sums: sum of any rectangle
For a grid, let P[i][j] be the sum of the rectangle from (0, 0) to (i − 1, j − 1). Then any rectangle sum is four lookups:
grid = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
R, C = len(grid), len(grid[0])
P = [[0] * (C + 1) for _ in range(R + 1)]
for i in range(R):
for j in range(C):
P[i + 1][j + 1] = grid[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j]
def rect(r1, c1, r2, c2): # inclusive corners
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]
print(rect(1, 1, 2, 2), rect(0, 0, 2, 2), rect(0, 1, 1, 2))
28 45 16
The − P[i][j] (and the + P[r1][c1]) fixes the corner that was added twice — the inclusion–exclusion idea.
4. Difference arrays: add to a whole range in O(1)
Problem: start with zeros, apply many updates "add v to every element in [l, r]", then print the final array. Doing each update element by element is O(n) per update.
Instead keep a difference array d (one cell longer than the result). For each update, do just two things: d[l] += v and d[r + 1] −= v. At the end, a running sum of d gives the final values.
def apply_updates(n, updates):
d = [0] * (n + 1)
for l, r, v in updates:
d[l] += v
d[r + 1] -= v
out, run = [], 0
for i in range(n):
run += d[i]
out.append(run)
return out
print(apply_updates(8, [(1, 4, 5), (3, 6, 2)]))
[0, 5, 5, 7, 7, 2, 2, 0]
m updates on n elements now cost O(n + m) instead of O(n · m). Real uses: "how many trains are at the station at each minute", "car pooling", "flight bookings", "corporate flight bookings".
5. How to recognise these problems
| The problem says… | Reach for |
|---|---|
| many "sum from l to r" questions on a fixed array | prefix sums |
| count / longest subarray with sum k (negatives allowed) | prefix sums + hash map |
| sum of a rectangle in a grid | 2D prefix sums |
| many "add v to a range", then one final read | difference array |
| updates and queries mixed together | Fenwick tree or segment tree (later lesson) |
Common mistakes
- Off-by-one: the sum of
a[l..r]isP[r + 1] − P[l], notP[r] − P[l]. - Forgetting
seen = {0: 1}, which misses subarrays that start at index 0. - Using the sliding window for "subarray sum k" when the array has negatives — it only works for positive numbers.
- Making the difference array length
ninstead ofn + 1, sod[r + 1]falls off the end. - Overflowing
intwith large prefix sums in Java or C++.
Quick recap
P[i]= sum of the firstiitems;sum(l, r) = P[r + 1] − P[l]in O(1).- Prefix sum + hash map counts subarrays with sum
kin O(n), even with negatives. - 2D prefix sums give any rectangle sum with four lookups.
- Difference array:
d[l] += v,d[r + 1] −= v, then one running sum — O(1) per range update.