Prefix Sums

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

Build the prefix (or prefix-product) array	O(n)
Range query, after the array is built	O(1)
Range query, re-summed from scratch (for comparison)	O(n) per query
Difference-array range update	O(1) per update, O(n) to reveal final values

The Idea

Imagine an odometer that, at every mile marker along a road, already tells you the total distance driven from the very start. Want to know the distance between mile marker 12 and mile marker 47? You don't redrive the road — you read the odometer at 47, read it at 12, and subtract. A prefix-sum array is exactly that odometer, built once for a list of numbers: precompute the running total up through every position, and afterward, the sum of any stretch [i, j] is just one subtraction away.

This only pays off because the running totals are computed once and reused many times. Building the odometer readings costs one pass over the whole road — O(n). But every question about a stretch of road after that costs a single subtraction — O(1) — instead of re-adding that stretch from scratch every time someone asks.

The trade: O(n) to build the prefix array once, in exchange for O(1) per range-sum query afterward — versus O(n) per query if you re-sum the range from scratch every single time someone asks.

Build It

The prefix array

// prefix[0] = 0                        // empty range sums to 0 — padding that avoids
                                          // special-casing "what if the range starts at 0"
// prefix[i] = prefix[i - 1] + arr[i - 1]  // running total through the first i original elements
// prefix has length n + 1 for an original array of length n — one extra leading slot

build the prefix array — O(n)

function buildPrefix(arr):
    n = length(arr)
    prefix = array of size n + 1
    prefix[0] = 0
    for i from 1 to n:
        prefix[i] = prefix[i - 1] + arr[i - 1]
    return prefix

range sum query [i, j] — O(1)

function rangeSum(prefix, i, j):
    // sum of arr[i..j] inclusive = everything through j, minus everything before i
    return prefix[j + 1] - prefix[i]

prefix[j + 1] is the total through index j; prefix[i] is the total through index i - 1 (everything strictly before the range starts). Subtracting removes exactly the part outside [i, j].

prefix product — same trick, different operator

function buildPrefixProduct(arr):
    n = length(arr)
    prefix = array of size n + 1
    prefix[0] = 1                      // empty product is 1, not 0
    for i from 1 to n:
        prefix[i] = prefix[i - 1] * arr[i - 1]
    return prefix

Nothing about the prefix idea is specific to addition — any operation where "undo the earlier part" makes sense (multiplication with division, for instance) can be precomputed the same way.

difference array — O(1) range updates, revealed with a prefix sum

function applyRangeAdd(diff, i, j, value):
    diff[i] += value          // start adding 'value' from index i onward
    diff[j + 1] -= value        // cancel that addition from index j + 1 onward

function reveal(diff):
    return buildPrefix(diff)   // a prefix sum over the diffs turns "start/stop" markers
                                // back into the real per-index totals, in one O(n) pass

The mirror image of a prefix sum: instead of precomputing totals to answer queries fast, a difference array records changes at the edges of a range so that many range updates can each be done in O(1) — the real values only get reconstructed once, at the end, with a single prefix-sum pass.

Know It

The whole point is moving the cost: pay once, up front, to build the array; every query after that is arithmetic, not a walk.

Operation	Time	Space	Why
Build the prefix (or prefix-product) array	O(n)	O(n)	One pass over the input, carrying a running total (or product) forward one slot at a time.
Range query, after the array is built	O(1)	O(1)	A range sum is one subtraction of two already-computed totals — no walking the range itself.
Range query, re-summed from scratch (for comparison)	O(n) per query	O(1)	Without a prebuilt prefix array, every query has to add up its own range again — the cost the prefix array exists to eliminate.
Difference-array range update	O(1) per update, O(n) to reveal final values	O(n)	Each update only touches two positions (the range's start and one past its end); the real per-index values only get reconstructed once, via a single prefix-sum pass over the diffs.

Break It

Off-by-one on the extra leading zero

indexing the prefix array as if it were the same length as the original

The prefix array has length n + 1, not n — prefix[0] = 0 is real padding, not an accident. Forgetting it (or forgetting the "+1" when translating a range [i, j] into prefix[j + 1] - prefix[i]) is the single most common bug in prefix-sum code — it silently shifts every range sum by one element.

Stale prefix sums after the data changes

the original array is modified after the prefix array was built

A prefix array is a snapshot. If arr[5] changes after buildPrefix ran, every prefix[i] for i > 5 is now wrong, and rangeSum will silently return stale answers instead of failing loudly. Either rebuild the whole prefix array after a change (O(n)) or use a structure designed for updates — that's a different tool for a later phase.

Negative numbers break "the answer is just the range"

finding the best-sum range in an array that has negative numbers

With all-positive numbers, the biggest-sum subarray is trivially the whole array. With negatives mixed in, that's no longer true, and "which two prefix values, subtracted, give the best result" stops being obvious from position alone — you need to remember which prefix-sum values you've already seen and where, which motivates pairing prefix sums with a fast-lookup structure (the next topic's whole subject) rather than a plain scan.

Use It

Range Sum Query - Immutable

Build the prefix array once in the constructor; every sumRange(i, j) call afterward is just prefix[j + 1] - prefix[i], no loop.

Easy

Find Pivot Index

At index i, the left-side sum is prefix[i] and the right-side sum is (total - prefix[i] - arr[i]) — walk once, comparing those two, instead of re-summing either side from scratch at every index.

Easy

Running Sum of 1d Array

This IS the prefix array — the answer at index i is literally the running total through i, exactly as defined in Build It, just returned directly instead of feeding a range query.

Easy

Shuffle the Array

No running total needed here, just index math: the value that belongs at output position 2i is x[i], and at 2i + 1 is y[i] — walk once and place directly, the same "array as addressable slots" idea from Arrays & Strings Fundamentals.

Easy

Contiguous Array

Treat every 0 as -1 and take a running sum (the prefix-sum idea from Build It) — a subarray is balanced exactly when its running sum returns to a value it already hit before. Remember the earliest index where each running-sum value first appeared (a lookup formalized as its own tool next topic); the gap between that first index and now is the length of a balanced subarray.

Medium

Product of Array Except Self

The prefix-product operation from Build It, run twice: a prefix-product pass (product of everything before i) times a suffix-product pass (product of everything after i) gives the answer at each index, without ever dividing.

Medium

Subarray Sum Equals K

Running sum again — a subarray sums to k exactly when an earlier running sum equals (current running sum - k). Keep a lookup of how many times each running-sum value has occurred so far (the fast-lookup structure the next topic formalizes) and add its count every time you see a match.

Medium

Corporate Flight Bookings

The difference-array trick from Build It: instead of adding seats to every day in [first, last], add once at first and subtract once at (last + 1). Running a prefix sum over that difference array at the end reveals the real per-day totals in one pass.

Medium

Minimum Value to Get Positive Step by Step Sum

Walk the running sum exactly like building the prefix array, tracking its minimum value along the way. The answer is 1 minus that minimum, clamped so it's never below 1.

Easy

Find the Highest Altitude

The running sum IS the altitude at each point — build the prefix array over the gain array and take its maximum value.

Easy