Prefix Sum

Store the running total of an array once, then answer any range sum by one subtraction, and count subarrays with a given sum by looking up earlier totals in a hash map.

Overview

The idea

A prefix sum is the total of the first i elements of an array. Write the totals down once, in an array prefix with prefix[0] = 0 and prefix[i] = prefix[i - 1] + nums[i - 1]. Then the sum of any range nums[l..r] is one subtraction: prefix[r + 1] - prefix[l]. The elements before l are counted in both totals, so they cancel.

The extra zero at the front matters. It means a range that starts at index 0 is handled by the same formula as any other range, with nothing special to check.

This table builds the array for [2, 4, 1, 5, 3, 7].

0 — none — 0 — sum of no elements
1 — 2 — 2 — 2
2 — 4 — 6 — 2 + 4
3 — 1 — 7 — 2 + 4 + 1
4 — 5 — 12 — 2 + 4 + 1 + 5
5 — 3 — 15 — 2 + 4 + 1 + 5 + 3
6 — 7 — 22 — the whole array

Three queries on that array follow, each one a single subtraction.

nums[2..4] — prefix[5] - prefix[2] = 15 - 6 — 9 — 1 + 5 + 3
nums[0..5] — prefix[6] - prefix[0] = 22 - 0 — 22 — the whole array
nums[3..3] — prefix[4] - prefix[3] = 12 - 7 — 5 — one element

Why it pays off

Adding up a range by hand costs as many steps as the range is long. With many queries on an array that does not change, the one-time build is cheap and every query after it is O(1).

Sum the range each time — none — O(length of the range) — up to 10 billion additions
Prefix sums — O(n) — O(1) — about 200,000 operations

The worst case for the first row is n × q = 100,000 × 100,000 = 10,000,000,000 additions. The second row is n additions to build plus q subtractions to answer: 200,000.

Counting subarrays with sum k

The second use is less obvious and appears in far more problems. A subarray nums[l..r] has sum k exactly when prefix[r + 1] - prefix[l] = k, which is the same as prefix[l] = prefix[r + 1] - k. So while you scan and compute the running total, ask: how many earlier totals equal the running total minus k? Each one is a subarray that ends here and sums to k.

A hash map from total to how many times it has appeared answers that in O(1). The map starts as {0: 1}, because the empty prefix has total 0 and has been seen once before the scan starts. Without it, every subarray that begins at index 0 is missed.

This trace runs on [1, 2, 1, 2, 1] with k = 3.

start — 0 — 0 — {0: 1}
0 — 1 — 1 — -2 — 0 — 0 — {0: 1, 1: 1}
1 — 2 — 3 — 0 — 1 — 1 — {0: 1, 1: 1, 3: 1}
2 — 1 — 4 — 1 — 1 — 2 — {0: 1, 1: 1, 3: 1, 4: 1}
3 — 2 — 6 — 3 — 1 — 3 — {…, 6: 1}
4 — 1 — 7 — 4 — 1 — 4 — {…, 7: 1}

The four subarrays are [1, 2], [2, 1], [1, 2] and [2, 1]. The scan is O(n) time and O(n) space, and it works with negative numbers, where a sliding window would not.

Sums divisible by k

Two totals with the same remainder when divided by k differ by a multiple of k, so the subarray between them has a sum divisible by k. Store remainders instead of totals in the map, and the count works exactly as above.

This trace runs on [4, 5, 0, -2, -3, 1] with k = 5.

start — 0 — 0 — 0
0 — 4 — 4 — 4 — 0 — 0
1 — 5 — 9 — 4 — 1 — 1
2 — 0 — 9 — 4 — 2 — 3
3 — -2 — 7 — 2 — 0 — 3
4 — -3 — 4 — 4 — 3 — 6
5 — 1 — 5 — 0 — 1 — 7

The seven subarrays match an exhaustive check.

> [!WARNING] > The remainder of a negative number depends on the language. In Python, -7 % 5 is 3 because % takes the sign of the divisor. In Java, -7 % 5 is -2 because % takes the sign of the dividend, so two totals that differ by a multiple of k can land in different buckets. Normalize with ((total % k) + k) % k, or use Math.floorMod in Java.

Longest subarray with a balance of zero

Some problems hide a sum. In Contiguous Array you want the longest run with as many 0s as 1s. Count each 1 as +1 and each 0 as -1; now you want the longest subarray with sum 0, which means two positions with the same running total. Store the first index where each total appears, and the length between a repeat and that first index is a candidate.

The map starts as {0: -1}: total 0 was first seen just before index 0, so a run that starts at index 0 gets the right length.

This trace runs on [0, 1, 0, 0, 1, 1, 0].

0 — 0 — -1 — new — 0
1 — 1 — 0 — -1 — 2 — 2
2 — 0 — -1 — 0 — 2 — 2
3 — 0 — -2 — new — 2
4 — 1 — -1 — 0 — 4 — 4
5 — 1 — 0 — -1 — 6 — 6
6 — 0 — -1 — 0 — 6 — 6

The answer is 6: nums[0..5] has three 0s and three 1s. The two map styles are the whole difference between the counting and the longest problems.

How many subarrays — total, count of times seen — {0: 1} — add the count to the answer
Longest subarray — total, first index seen — {0: -1} — candidate length i - first
Shortest subarray — total, latest index seen — {0: -1} — candidate length i - latest

Two dimensions

A 2D prefix array stores the sum of the rectangle from the top left corner to each cell. Build it with one extra row and column of zeros, and each cell adds the cell above and the cell to the left, then subtracts the overlap that was counted twice.

P[i][j] — M[i - 1][j - 1] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]
sum of rows r1..r2, cols c1..c2 — P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

Take the matrix with rows [1, 2, 3], [4, 5, 6] and [7, 8, 9]. Its prefix matrix P is one row and one column larger.

row 0 — 0 — 0 — 0 — 0
row 1 — 0 — 1 — 3 — 6
row 2 — 0 — 5 — 12 — 21
row 3 — 0 — 12 — 27 — 45

The sum of the bottom right 2 × 2 block (5, 6, 8, 9) is P[3][3] - P[1][3] - P[3][1] + P[1][1] = 45 - 6 - 12 + 1 = 28. The build is O(rows × cols) and each rectangle query is O(1).

The same trick with other operations

Range subtraction works because addition has an inverse. Any operation with an inverse gets the same one-subtraction query.

Sum — running total — prefix[r + 1] - prefix[l] — integer overflow in fixed-width languages
XOR — running XOR — prefix[r + 1] ^ prefix[l] — none; XOR is its own inverse
Product — running product — prefix[r + 1] / prefix[l] — a zero anywhere breaks division
Max or min — running max — not possible — max has no inverse; use a sparse table or segment tree

For products, the usual move avoids division entirely. Product of Array Except Self multiplies a prefix product from the left by a suffix product from the right, so zeros need no special case.

Range updates: the inverse operation

A difference array is the prefix sum run backwards. To add v to every element of nums[l..r], write d[l] += v and d[r + 1] -= v. After all updates, a prefix sum of d gives the final array. Each update is O(1) no matter how long the range is.

Two updates on an array of six zeros, add 2 to [1..3] and add -1 to [2..5]:

d after both updates — 0 — 2 — -1 — 0 — -2 — 0 — 1
prefix sum of d — 0 — 2 — 1 — 1 — -1 — -1

Index 2 and 3 got both updates (2 - 1 = 1), index 4 and 5 got only the second (-1). Reading the result costs O(n) once, after all updates.

When the array changes

Prefix sums assume the array is fixed. One changed element changes every total after it, an O(n) rebuild. If updates and queries are mixed, a Fenwick tree (also called a binary indexed tree) or a segment tree does both in O(log n).

Prefix sum array — O(n) rebuild — O(1) — tiny
Fenwick tree — O(log n) — O(log n) — small
Segment tree — O(log n) — O(log n), and range max, min, or range updates with lazy propagation — larger

Ask whether the array changes before you commit. Static means prefix sums; changing means a tree.

How to spot it

Many range sum queries on a fixed array — prefix array, subtract
Count subarrays whose sum equals k, with negatives allowed — running total plus a count map starting at {0: 1}
Subarray sum divisible by k — remainders in the map, normalize negatives
Longest subarray with equal counts, or with sum 0 — +1 and -1, first-index map starting at {0: -1}
Rectangle sums in a matrix — 2D prefix, four-term formula
Add v to a range, many times, then read the array — difference array
Range sum with updates in between — Fenwick tree or segment tree

What you will be able to do

Build a prefix array with the leading zero and answer any range sum in O(1).
Count subarrays with sum k, or divisible by k, in one pass with a hash map.
Turn equal-count and balance problems into a sum-0 problem with a first-index map.
Extend the idea to matrices, XOR and range updates.
Say when prefix sums stop working and a Fenwick or segment tree is needed.

When to use it

Many range sum queries on an array that does not change
Count or find subarrays whose sum equals a target, including with negative numbers
Subarrays whose sum is divisible by k (remainders of the running total)
Longest or shortest subarray with sum 0, or with equal counts of two values
Rectangle sums in a matrix (2D prefix sums)
Many range updates followed by one read of the array (difference array)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio