Prefix Sum

Prefix Sum | Algoryva

for

Intuition

Your car's odometer already does this

Suppose your odometer read 12,400 km when you left home and 12,465 km when you arrived. How long was the trip? You did not add up every kilometre: you subtracted 65 = 12,465 − 12,400.

The odometer keeps a running total from the day the car was built. Any trip between two moments is the difference of two readings. A prefix array is an odometer for your array: it stores the running total at every position, so the sum of any stretch is one subtraction.

First, the naive way

Answer each query by adding the range

You are given an array a and many questions of the form “what is the sum from index l to index r?”. The direct answer loops over the range every time.

Look at what the loop wastes. The queries [1, 3] and [0, 4] overlap, yet each one re-adds a[1] + a[2] + a[3] from scratch. Nothing is remembered between queries, so the same additions are done again and again.

python

def range_sum_naive(a, l, r):
    total = 0
    for i in range(l, r + 1):
        total += a[i]
    return total

Cost: O(n) per query, so O(n × q) overall. With n = q = 200,000 that is about 4 × 10^10 additions: far beyond the roughly 10^8 a program can do in a second.

The observation

A range sum is a difference of two sums that start at the front

The sum of a[l..r] equals “everything from the start up to r” minus “everything from the start up to just before l”. Everything before l appears in both and cancels, exactly like the odometer.

So store, once, the sum of the first k elements for every k. Call it P[k], with P[0] = 0 because the sum of zero elements is zero. Then: sum(a[l..r]) = P[r + 1] − P[l].

The leading 0 is not decoration. It lets l = 0 work with no special case, because P[0] is simply 0.

See it move

Build P once, then query it

Watch the first phase: each new P[i+1] is the previous P[i] plus one array element, so building costs one pass. Then watch the queries: the highlighted part of the array is the range, and the two coloured cells in P are the only two values used.

Worked by hand

The same array, by hand

Take a = [2, 4, 1, 5, 3, 6]. Here is P, aligned so that P[k] is the sum of the first k elements (note that P has one more entry than a).

k	0	1	2	3	4	5	6
a[k-1]	·	2	4	1	5	3	6
P[k]	0	2	6	7	12	15	21

1
Sum of a[1..3]
P[3 + 1] − P[1] = P[4] − P[1] = 12 − 2 = 10. Check by hand: 4 + 1 + 5 = 10.
2
Sum of a[0..4]
P[5] − P[0] = 15 − 0 = 15. The leading zero makes the “from the start” case work with the same formula.

Implementation

Prefix sums in Python

Plan first, then code. The plan has two functions: one pass to build, one subtraction to query.

Plan in plain steps

pseudocode

P = list of n + 1 zeros
for each index i from 0 to n - 1:
    P[i + 1] = P[i] + a[i]
to answer (l, r):  return P[r + 1] - P[l]

python

def build_prefix(a):
    P = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        P[i + 1] = P[i] + x
    return P

def range_sum(P, l, r):      # inclusive, 0-indexed
    return P[r + 1] - P[l]

a = [2, 4, 1, 5, 3, 6]
P = (a)
((P, , ))

The concept

The variants you will meet

The idea has a few standard shapes. They differ only in what is stored and what the formula subtracts.

Running sum: you only need the current total, so you keep one variable instead of an array (for example “how many points so far”).
Inclusive vs exclusive prefix: an inclusive array S[i] includes a[i]; an exclusive one excludes it. Our P is the exclusive form shifted by one, which is why it needs the leading 0. Pick one convention per problem and stay with it.
2D prefix sum: P[i][j] is the sum of the rectangle from the top-left corner to just before row i, column j. A rectangle query uses four lookups.
Difference array: the reverse operation. Instead of summing a range cheaply, you *add to a range* cheaply, then rebuild the array with one prefix sum.

Implementation

Rectangle sums in a grid

To build P[i + 1][j + 1], add the cell to the block above and the block to the left. Those two blocks overlap in the block above-and-left, which got counted twice, so subtract it once. A query uses the same inclusion and exclusion: take the big rectangle, cut away the strip above and the strip to the left, and add back the corner that was cut twice.

python

def build_2d(grid):
    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]
    return P

def rect_sum(P, r1, c1, r2, c2):   # inclusive corners, 0-indexed
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

Implementation

Many range updates: the difference array

Now the opposite problem. You get many updates of the form “add k to every element from l to r”, and only at the end do you need the array. Doing each update with a loop is O(n) each again.

Place a +k at position l and a −k at position r + 1. When you take the prefix sum of that difference array, the +k switches the boost on at l and the −k switches it off after r. Every update costs O(1), and one pass at the end applies them all.

python

def apply_range_adds(n, updates):      # updates: (l, r, k), 0-indexed inclusive
    diff = [0] * (n + 1)               # one spare slot for r + 1 == n
    for l, r, k in updates:
        diff[l] += k
        diff[r + 1] -= k
    result, running = [], 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result

print(apply_range_adds(5, [(, , ), (, , )]))

Complexity

Why these costs

The pattern is always the same: pay O(n) once to build, then every question is constant time.

Build the 1D prefix array

time O(n)space O(n)

One pass, one stored value per element (plus the leading zero).

One range-sum query

time O(1)space O(1)

Two array reads and one subtraction, regardless of range length.

Naive, for comparison

time O(n) per queryspace O(1)

Loops over the range every time, so q queries cost O(n × q).

2D build, then a rectangle query

time O(R·C) then O(1)space O(R·C)

Each cell is computed once from three neighbours; a query is four lookups.

Difference array with q updates

time O(n + q)space O(n)

Each update touches two cells; one final pass rebuilds the array.

Edge cases

Cases that trip people up

l = 0Works with no special case because P[0] = 0. If you skipped the leading zero you would need an if.
Single element (l = r)P[l + 1] − P[l] is just a[l]. Good sanity test for your indexing.
Negative numbersNo problem. Prefix sums never assume values are positive (unlike the variable sliding window).
1-indexed inputMany problems give l and r starting at 1. Convert once when you read them (l -= 1; r -= 1) instead of adjusting inside formulas.
Huge sumsPython integers do not overflow. In C++ or Java use a 64-bit type for P, since n × max(a) can exceed 2^31.
Empty arrayP = [0] and no valid query exists. Make sure your build code does not index a[0].

Common mistakes

Mistakes to avoid

Writing P[r] − P[l] for an inclusive range.
That drops a[r]. With the leading-zero convention it is P[r + 1] − P[l]. Test a one-element range to catch this.
Forgetting the leading zero, then special-casing l = 0.
Start P with 0. Fewer branches means fewer bugs.
Mixing 0-indexed arrays with 1-indexed queries.
Convert at input time, once. Never let two index conventions meet in a formula.
Rebuilding the prefix array inside the query loop.
Build before the loop. Building per query turns O(n + q) back into O(n × q).
Using a prefix array when values change between queries.
Each change would invalidate O(n) entries. Use a Fenwick or segment tree instead.

Recognize it in a contest

How to spot a prefix-sum problem

In a contest you will rarely see the words “prefix sum”. You will see a shape. Learn the shapes.

Reach for it when the problem says or implies

Many queries of the form “sum (or count, or xor) of the elements between positions l and r” on data that does not change.
“Count the subarrays whose sum equals k”. A subarray sum is P[j] − P[i], so you are looking for two prefix values that differ by k.
“Apply many range additions, then print the final array”. That is the difference array.
A condition about a *balance*: equal numbers of 0s and 1s, or matching brackets. Map the items to +1/−1; a balanced stretch is one where the running total returns to an earlier value.
Constraints around 2 × 10^5 for both the array and the number of queries, where O(n × q) cannot pass.

Look elsewhere when

Worked problem

Count subarrays with sum exactly k

The problem

Given an array of integers (values may be negative) and a number k, count how many contiguous non-empty subarrays have sum exactly k.

Naive idea: try every pair (i, j) and sum it, which is O(n²) or worse, too slow for n = 2 × 10^5.
A subarray a[i..j-1] has sum P[j] − P[i]. We want that to equal k, so P[i] = P[j] − k.
Scan left to right keeping the running prefix value. For each new prefix value, add how many *earlier* prefix values equal running − k.
Keep a dictionary counting prefix values seen so far. Start it with {0: 1} for the empty prefix, so subarrays starting at index 0 are counted.

python

from collections import defaultdict

def count_subarrays_with_sum(a, k):
    seen = defaultdict(int)
    seen[0] = 1                 # the empty prefix
    running = count = 0
    for x in a:
        running += x
        count += seen[running - k]
        seen[running] += 1
    return count

print(count_subarrays_with_sum([, , , -, ], ))

Worked problem

Find the pivot index

The problem

Find the leftmost index whose left-side sum equals its right-side sum (the element itself is excluded from both). Return -1 if there is none.

For index i, the left sum is P[i] (everything before i).
The right sum is total − P[i + 1] (everything after i).
Test each i in O(1) and return the first match.

python

def pivot_index(a):
    P = [0]
    for x in a:
        P.append(P[-1] + x)
    total = P[-1]
    for i in range(len(a)):
        if P[i] == total - P[i + 1]:
            return i
    return -1

print(pivot_index([1, 7, 3, 6, 5, 6]))   # 3

Wrap-up

Remember this

A range sum is a difference of two prefix sums, so one precomputation makes every query O(1).
Use P with a leading zero: sum(a[l..r]) = P[r + 1] − P[l]. Convert input to 0-indexed once.
Reverse the trick for updates: +k at l, −k at r + 1, then one prefix sum rebuilds the array.
Subarray-sum problems become “find two prefix values that differ by k”, solved with a dictionary.
Prefix sums need an undoable operation and unchanging data; otherwise reach for a Fenwick or segment tree.

Cheat sheet

Build (1D): P[0] = 0; P[i+1] = P[i] + a[i] → O(n)
Range sum a[l..r]: P[r+1] − P[l] → O(1)
Rectangle (2D): P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]
Range add (difference array): diff[l] += k; diff[r+1] −= k; then prefix-sum diff
Subarray sum = k: count += seen[running − k]; seen[running] += 1
Works for: sum, count, xor (operations you can undo). Not max / min / gcd.

Top traps to avoid

Writing P[r] − P[l] for an inclusive range.
Forgetting the leading zero, then special-casing l = 0.
Mixing 0-indexed arrays with 1-indexed queries.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.For a = [3, 1, 4, 1, 5] the prefix array (with leading zero) is [0, 3, 4, 8, 9, 14]. What is the sum of a[1..3]?
2.Why do we put a 0 at the front of the prefix array?
3.Which task is not a good fit for a plain prefix-sum array?
4.With n = q = 200,000, roughly how many basic steps do the naive and the prefix approaches take?
5.With n = 5, updates add 2 to [1, 3] and add 1 to [2, 4]. After applying a difference array, what is the final array (all zeros at the start)?
6.Which of these can be answered with prefix-style precomputation?
7.prefix = [0]; for x in [2, -1, 3]: prefix.append(prefix[-1] + x). What does prefix[3] - prefix[1] give?
8.How many subarrays of [1, 1, 1] have sum exactly 2?
9.In nums = [1, 2, 3] with k = 3, how many contiguous subarrays sum to k?
10.Using a prefix array P for [5, 5, 5], what is P[2]?
11.For nums = [1, -1, 1, -1], how many subarrays have sum 0?
12.Why does a prefix array need n + 1 entries, with P[0] = 0?
13.After O(n) preprocessing, how long does one range-sum query take?
14.Which formula gives the sum of a rectangle in a 2D prefix-sum table (1-indexed, P[r][c] = sum of the top-left block)?
15.Why are prefix sums built from a running total, rather than summing each range directly?

Prefix Sum

After this lesson you will be able to

Builds on

Unlocks

Your car's odometer already does this

Answer each query by adding the range

A range sum is a difference of two sums that start at the front

Build P once, then query it

The same array, by hand

Prefix sums in Python

The variants you will meet

Rectangle sums in a grid

Many range updates: the difference array

Why these costs

Cases that trip people up

Mistakes to avoid

How to spot a prefix-sum problem

Count subarrays with sum exactly k

Find the pivot index

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core4 problems

Application3 problems

Challenge1 problem

Reading the code

Reading the code

Reading the code