Prefix Sums
Precompute running totals so any range-sum query becomes O(1) - the trick behind subarray-sum and equilibrium problems.
On this page
Some problems ask the sum of a range over and over: "sum from index i to j," many times, for different i and j. Computing each range by looping is O(n) per query. Prefix sums precompute once so every range-sum query afterward is O(1) - a small idea with outsized leverage.
Precompute the running totals
Build an array prefix where prefix[i] is the sum of the first i elements. Then the sum of any
range [i, j) is just a subtraction:
// prefix[i] = a[0] + a[1] + ... + a[i-1]
int[] prefix = new int[a.length + 1];
for (int i = 0; i < a.length; i++)
prefix[i + 1] = prefix[i] + a[i];
// sum of a[i..j-1] in O(1), no matter how big the range
int rangeSum(int i, int j) {
return prefix[j] - prefix[i];
}One O(n) precomputation, then every range query is a single subtraction. If a problem does many range-sum queries, this collapses an O(n·q) solution to O(n + q).
The real power: subarray-sum problems
Prefix sums shine on "count subarrays that sum to k." The insight: a subarray (i, j] sums to k
exactly when prefix[j] - prefix[i] == k, i.e. prefix[i] == prefix[j] - k. So as you sweep,
you ask a hash map how many earlier prefixes had the value you need:
// number of subarrays summing to k — O(n) with prefix sums + a hash map
int subarraySum(int[] a, int k) {
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1); // empty prefix
int prefix = 0, count = 0;
for (int x : a) {
prefix += x;
count += seen.getOrDefault(prefix - k, 0); // earlier prefixes that complete a k-sum
seen.merge(prefix, 1, Integer::sum);
}
return count;
}This is the two-patterns-combine moment from the catalog: prefix sums + hashing turns an O(n²) double loop into a single O(n) pass. It even works with negative numbers, where a sliding window would fail.
Prefix sums extend to 2D and to products
The same trick generalizes. A 2D prefix-sum matrix answers submatrix-sum queries in O(1). A prefix-product (or prefix-XOR) handles range products and range XORs. Whenever you see repeated range aggregation, ask whether a prefix structure precomputes it.
To know the distance between exit 12 and exit 47, you don't re-measure the road - you read the mile markers and subtract: 47's marker minus 12's. The markers are a one-time survey (the prefix array); after that, any stretch's length is a single subtraction. Prefix sums are mile markers for an array: survey the running totals once, then every range is marker minus marker.
You're given an array and asked to answer q queries, each asking for the sum of a range [i, j]. Naively each query loops the range. Explain how prefix sums change the total complexity from O(n·q) to O(n + q), and what the answer to a single query becomes.
After building a prefix-sum array, what is the cost of answering one range-sum query?
Key takeaways
- Prefix sums precompute running totals so any range sum is prefix[j] - prefix[i] in O(1).
- One O(n) build turns many range queries from O(n*q) into O(n + q).
- Prefix sums + a hash map count subarrays summing to k in O(n), even with negative numbers.
- The pattern generalizes: 2D prefix sums for submatrices, prefix products/XOR for other range aggregations.
- The tell is repeated range aggregation - precompute once, then subtract.