On this page
Description
A prefix sum is the running total of an array: prefix[i] is the sum of the first i elements. Build it once in O(n), and the sum of any range becomes a single subtraction. Without it, every "sum of nums[l..r]" question adds the range up again, O(n) per query. Paired with a hash map, the same running total also finds subarrays that add up to a given value in one pass. That works even with negative numbers, where a sliding window fails.
We'll go from simple to more technical:
- The pattern: a padded prefix array and one subtraction per query.
- Prefix sum plus a hash map: subarrays that sum to k.
- Where the same idea runs in production (cumulative reports, rollups).
- When it applies, and when updates make it the wrong tool.
The approach
Make the prefix array one longer than the input and set prefix[0] = 0. Then prefix[i + 1] = prefix[i] + nums[i]. The sum of nums[l..r] is everything up to r, minus everything before l.
For nums = [2, -1, 3, 4, -2]:
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
nums[i] | 2 | -1 | 3 | 4 | -2 | |
prefix[i] | 0 | 2 | 1 | 4 | 8 | 6 |
The sum of nums[1..3] is prefix[4] - prefix[1] = 8 - 2 = 6, which is -1 + 3 + 4.
Java
int[] prefix = new int[nums.length + 1]; // prefix[0] = 0 by convention
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
// sum of nums[l..r] inclusive:
int rangeSum = prefix[r + 1] - prefix[l];
Python
prefix = [0] * (len(nums) + 1) # prefix[0] = 0 by convention
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
# sum of nums[l..r] inclusive:
range_sum = prefix[r + 1] - prefix[l]
The extra prefix[0] = 0 is what lets a range start at index 0 without a special case.
A second flavor: prefix sum + hash map
Some questions aren't "build once, answer many queries". The longest subarray that sums to exactly k walks the array once. At each index it asks: did some earlier prefix sum to exactly sum - k? If so, the elements between that point and here add up to k.
Java
Map<Integer, Integer> firstIndexOfSum = new HashMap<>();
firstIndexOfSum.put(0, -1); // an empty prefix (before index 0) sums to 0
int sum = 0, best = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (firstIndexOfSum.containsKey(sum - k)) {
best = Math.max(best, i - firstIndexOfSum.get(sum - k));
}
firstIndexOfSum.putIfAbsent(sum, i); // keep the EARLIEST index for a given prefix sum
}
Python
first_index_of_sum = {0: -1} # an empty prefix (before index 0) sums to 0
total = best = 0
for i, x in enumerate(nums):
total += x
if total - k in first_index_of_sum:
best = max(best, i - first_index_of_sum[total - k])
first_index_of_sum.setdefault(total, i) # keep the EARLIEST index for a given prefix sum
Take the same array and k = 5. At index 4 the running sum is 6. The prefix up to index 1 summed to 1, which is 6 - 5. So [3, 4, -2], from index 2 to 4, sums to 5, and the best length is 3. The map keeps only the earliest index for each sum, because an earlier start gives a longer subarray.
Where you'll see it
Any "total as of date X" report is a prefix sum over a table sorted by time: a running account balance, or cumulative signups by day. Analytics systems keep precomputed rollup tables for the same reason. The idea is identical; only the storage is a database instead of an array.
Which tool for which job?
| You need | Use |
|---|---|
| Many range sums over an array that doesn't change | a prefix-sum array |
| Subarrays summing to k (negatives allowed) | prefix sum + hash map |
| Subarrays whose sum is divisible by k | prefix sum mod k + hash map |
| Many range updates, then reads | a difference array |
| Range sums with frequent point updates | a Fenwick tree (O(log n) each) |
| Sums of rectangles in a grid | a 2D prefix sum |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Rebuilding the prefix array per query | right answers, O(n) per query | build once, before the queries |
No prefix[0] = 0 padding | special cases for ranges starting at 0 | size it n + 1 |
Mixing inclusive and exclusive r | off-by-one sums | prefix[r + 1] - prefix[l] for inclusive r |
No {0: -1} (or {0: 1}) seed in the map | subarrays starting at index 0 are missed | seed the empty prefix |
An int prefix array in Java | overflow on large totals | long[] |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A solution rebuilds the prefix array inside the query loop. Every test passes. Is it a good solution?
Show answer
Not necessarily. The answers are right, but each query costs O(n) instead of O(1). Tests that only check answers won't notice unless they're big enough to make the slow version time out. Passing tests shows the code is correct, not that the approach is right.
2. Why does the hash map start with {0: -1}?
Show answer
So a subarray that starts at index 0 can be found. If the running sum at index i equals k, then sum - k is 0. The entry for sum 0 at index -1 stands for "before the array starts", and the length i - (-1) = i + 1 covers the whole prefix.
3. The array changes often between range-sum queries. Should you still use a prefix array?
Show answer
Probably not. Each change costs O(n) to fix the prefix sums, which defeats the point. A Fenwick tree (also called a binary indexed tree) handles both updates and range sums in O(log n) each.
Key takeaways
- Build the prefix array once in O(n). Then every range sum is O(1):
prefix[r + 1] - prefix[l]. - The padding
prefix[0] = 0removes the special case for ranges that start at index 0. - Prefix sum plus a map of the earliest index per sum finds subarrays that sum to k in one pass, negatives included.
- Passing every test proves correctness, not the right approach.
- When the array changes often, use a Fenwick tree instead.