Overview
A prefix sum array stores the running total of an array: prefix[i] is the sum of the first i elements. After O(n) preprocessing, the sum of any range [l, r] is prefix[r + 1] - prefix[l], answered in O(1).
Prefix sums are the foundation for counting subarrays with a given sum, 2D region queries on grids, and difference arrays that apply range updates efficiently.
To know how far you drove between two cities, you do not add up every kilometre again. You subtract the odometer reading at the first city from the reading at the second. prefix[] is the odometer.
When to use it
- Many range-sum queries on an array that does not change.
- Count or find subarrays whose sum equals, or is divisible by, a value (combined with a hash map).
- Rectangle sums on a 2D grid.
- Balance problems such as equal numbers of 0s and 1s (map 0 to -1, then prefix sum).
Problem patterns it solves
Recognize it when: many sum(l..r) queries on data that does not change.
- 303. Range Sum Query - Immutable
- 724. Find Pivot Index
- 1480. Running Sum of 1d Array
Recognize it when: count or find subarrays whose sum equals k, is divisible by k, or has a remainder; works with negative numbers.
- 560. Subarray Sum Equals K
- 523. Continuous Subarray Sum
- 974. Subarray Sums Divisible by K
- 1248. Count Number of Nice Subarrays
Recognize it when: equal numbers of two kinds; map one kind to -1 and look for equal prefixes.
- 525. Contiguous Array
- 1124. Longest Well-Performing Interval
Recognize it when: sum of any rectangle in a grid, many times.
- 304. Range Sum Query 2D - Immutable
- 1314. Matrix Block Sum
- 1074. Number of Submatrices That Sum to Target
Recognize it when: answer for i depends on everything left of i and everything right of i.
- 238. Product of Array Except Self
- 42. Trapping Rain Water
Where it is used in real software
A 2D prefix sum (summed-area table) lets face detectors such as Viola-Jones compute the sum of any rectangle of pixels in 4 lookups.
Running totals of revenue or signups let the dashboard answer 'total between two dates' with one subtraction.
Pre-aggregated cumulative counters make range aggregates over long periods cheap to query.
Editors keep cumulative line lengths so they can convert a character offset to a line number quickly.
Key terms
- prefix[i]
- Sum of values[0] through values[i - 1]; prefix[0] = 0.
- Range sum
- sum(l..r) = prefix[r + 1] - prefix[l].
- Difference array
- The inverse idea: store changes so a range update is two O(1) writes.
How it works, step by step
- 1Allocate n + 1 slots
prefix[0] = 0 represents the empty prefix and removes special cases for ranges starting at 0.
- 2Accumulate
prefix[i + 1] = prefix[i] + values[i] for every i.
- 3Answer queries
sum(l..r) = prefix[r + 1] - prefix[l].
- 4For subarray counts, use a map
A subarray ending at i sums to k exactly when an earlier prefix equals currentPrefix - k. Count earlier prefixes in a hash map.
STEP 1prefix[0] = 0 represents the empty prefix. It removes the special case for ranges that start at index 0.
Range sums on a small array
values = [3, 1, 4, 1, 5, 9]
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| values[i] | 3 | 1 | 4 | 1 | 5 | 9 | - |
| prefix[i] | 0 | 3 | 4 | 8 | 9 | 14 | 23 |
NOWi: values[i] | 0: 3 | 1: 1 | 2: 4 | 3: 1 | 4: 5 | 5: 9 | 6: -
sum(1..4) = prefix[5] - prefix[1] = 14 - 3 = 11, which matches 1 + 4 + 1 + 5. Any query is now one subtraction.
Implementation
function buildPrefix(values: number[]): number[] { const prefix = new Array<number>(values.length + 1).fill(0); for (let i = 0; i < values.length; i++) { prefix[i + 1] = prefix[i] + values[i]; } return prefix;} const rangeSum = (prefix: number[], l: number, r: number) => prefix[r + 1] - prefix[l]; // Count subarrays whose sum equals k (works with negative numbers).function subarraySum(values: number[], k: number): number { const seen = new Map<number, number>([[0, 1]]); let running = 0; let count = 0; for (const value of values) { running += value; count += seen.get(running - k) ?? 0; seen.set(running, (seen.get(running) ?? 0) + 1); } return count;}Complexity and performance
One pass over the input.
One subtraction per range.
n + 1 running totals.
Average O(1) hash map operations per element.
Trade-offs
An update at index i changes every later prefix, costing O(n). For frequent updates, use a Fenwick tree or segment tree with O(log n) update and query.
Running totals can exceed 32-bit integers. Use 64-bit types (long in Java, long long in C++).
Variants and related techniques
To add v to every element in [l, r], do diff[l] += v and diff[r + 1] -= v. A final prefix sum over diff reconstructs the array.
Any invertible operation works: prefix XOR answers range XOR queries the same way.
Subarrays divisible by k correspond to equal prefix values modulo k.
Common mistakes
- Off-by-one with prefix of length n.
Fix: Use length n + 1 with prefix[0] = 0 and the formula prefix[r + 1] - prefix[l].
- Forgetting to seed the map with {0: 1}.
Fix: Without it, subarrays starting at index 0 are never counted.
- Using a sliding window when values can be negative.
Fix: Prefix sum plus hash map handles negatives correctly.
Interview questions
Why does the subarray-sum-equals-k trick work?
sum(i+1..j) = prefix[j] - prefix[i]. It equals k exactly when prefix[i] = prefix[j] - k, so counting earlier prefixes with that value counts valid subarrays ending at j.
What changes if the array receives updates?
Use a Fenwick (binary indexed) tree or segment tree to support both point updates and range queries in O(log n).
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| Range Sum Query - Immutable | Easy | Build and query. |
| Find Pivot Index | Easy | Left sum vs total minus left. |
| Subarray Sum Equals K | Medium | Prefix sum plus hash map. |
| Contiguous Array | Medium | Map 0 to -1 and find equal prefixes. |
| Range Sum Query 2D - Immutable | Medium | Inclusion-exclusion. |
| Product of Array Except Self | Medium | Prefix and suffix products. |