Prefix Sums
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 |
Imagine an odometer. At each mile marker on a road, the odometer tells you the total distance from the start. You want to know the distance between mile marker 12 and mile marker 47. You do not drive the road again. You read the odometer at 47, read the odometer at 12, and subtract. A prefix-sum array is this odometer for a list of numbers. You compute the running total through each position one time. After that, the sum of any part [i, j] is one subtraction.
This is a good method because you compute the running totals one time and use them many times. To build the odometer readings costs one pass over the full road, which is O(n). But each question about a part of the road after that costs one subtraction, which is O(1). You do not add that part again each time someone asks.
The prefix array
// prefix[0] = 0 // An empty range sums to 0. This padding prevents
// a special case for "the range starts at 0".
// prefix[i] = prefix[i - 1] + arr[i - 1] // the running total through the first i original elements
// prefix has length n + 1 for an original array of length n. It has 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 prefixrange sum query [i, j] — O(1)
function rangeSum(prefix, i, j):
// The sum of arr[i..j] is the total through j, minus the total before i.
return prefix[j + 1] - prefix[i]prefix product — same trick, different operator
function buildPrefixProduct(arr):
n = length(arr)
prefix = array of size n + 1
prefix[0] = 1 // The empty product is 1, not 0.
for i from 1 to n:
prefix[i] = prefix[i - 1] * arr[i - 1]
return prefixdifference array — O(1) range updates, revealed with a prefix sum
function applyRangeAdd(diff, i, j, value):
diff[i] += value // Start to add 'value' from index i to the end.
diff[j + 1] -= value // Cancel that addition from index j + 1 to the end.
function reveal(diff):
return buildPrefix(diff) // A prefix sum over the diffs changes the start and stop
// markers back into the real per-index totals, in one O(n) pass.The main idea is to move the cost. You pay one time, at the start, to build the array. Each query after that is arithmetic, not a walk.
| Operation | Time | Space | Why |
|---|---|---|---|
| Build the prefix (or prefix-product) array | O(n) | O(n) | This is one pass over the input. It carries 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 totals that are already computed. You do not walk the range. |
| Range query, re-summed from scratch (for comparison) | O(n) per query | O(1) | Without a prebuilt prefix array, each query must add its own range again. This is the cost that the prefix array removes. |
| Difference-array range update | O(1) per update, O(n) to reveal final values | O(n) | Each update touches only two positions: the start of the range and one position after the end. You reconstruct the real per-index values one time, with one prefix-sum pass over the diffs. |
Off-by-one on the extra leading zero
The prefix array has length n + 1, not n. prefix[0] = 0 is real padding, not a mistake. If you forget it, or forget the "+1" when you translate a range [i, j] into prefix[j + 1] - prefix[i], you make the most common prefix-sum bug. It moves every range sum by one element with no error.
Stale prefix sums after the data changes
A prefix array is a snapshot. If arr[5] changes after buildPrefix runs, each prefix[i] for i > 5 is now wrong. rangeSum returns old answers with no error. You must build the full prefix array again after a change (O(n)), or use a structure made for updates. That structure is a different tool for a later phase.
Negative numbers break "the answer is just the range"
With only positive numbers, the biggest-sum subarray is the full array. With negative numbers mixed in, this is no longer true. The best pair of prefix values to subtract is no longer clear from position alone. You must remember which prefix-sum values you have seen and where. This is why you pair prefix sums with a fast-lookup structure (the subject of the next topic) instead of a plain scan.
Sign in to mark problems done — progress syncs across devices.