What is prefix sum?
Prefix sum precomputes a running total once — prefix[i] holds the sum of everything up to and
including index i. Once that array exists, the sum of any range [left, right] is just
prefix[right - prefix[left - 1]], an O(1) lookup instead of re-adding that stretch from scratch
every time. One setup pass pays for itself the moment you have more than one range to ask about.
- Prefix sum
- The running total of every value up to and including index i
- Range query
- Sum of
[left, right] found by subtracting two prefix values - Prefix sum + hashmap
- Track how many times each running total has occurred, to count subarrays
Why prefix sum at all?
Picture a car's trip odometer. It never resets — it just keeps adding the miles from every leg of the drive onto one running total.
Want to know how far you drove between mile-marker A and mile-marker B? You don't re-drive that stretch. You just read the odometer at B, read it at A, and subtract. Prefix sum does the same thing for an array: build the running total once, then answer any range by subtracting two readings.
Each leg only adds to the total that's already there. Nothing gets re-driven.
What kinds of problems does it solve?
Four common shapes. Every one of them leans on the same running total — what changes is what you do with it once it exists.
Answer a range sum instantly
Build prefix once in O(n). After that, the sum of [left, right] is
prefix[right - prefix[left - 1]] — one subtraction, no matter how wide the range is.
prefix[4] − prefix[1] gives the sum of indices 2..4 in one step.
Count subarrays with sum k
Walk once, keeping a running sum. At each step, check whether sum - k has been seen
before — if it has, every one of those earlier stops marks a subarray that sums to
k. This is the single most-tested prefix sum pattern in interviews.
Every earlier stop at sum − k is one more subarray that sums to k.
Find a balance point
Some problems ask for the index where the sum on one side equals the sum on the other. The
total is fixed, so the right-hand sum is always total - leftSum — no need to sum the
right side again at every index.
Left sum and right sum meet at index 3 — 11 on both sides.
Combine a prefix with a suffix
Build a running product from the left and a running product from the right. Multiply the two at each index and you get "everything except this index" — without ever dividing by the current value.
Index 2's answer is everything before it times everything after it — 2 × 4 = 8.
Two types
Underneath, it's really only two shapes: a plain running total you query directly, and a running total paired with a hashmap so you can count how many times a value has occurred.
Basic prefix sum + range query
Build prefix once, where prefix[i] is the sum of arr[0..i]. Pad with a
leading 0 so left = 0 never needs a special case. Every range query afterward is one
subtraction.
One O(n) build, then O(1) per query — forever.
function buildPrefixSums(arr: number[]): number[] {
const prefix = [0]; // prefix[0] = 0 so left = 0 needs no special case
for (let i = 0; i < arr.length; i++) {
prefix.push(prefix[i] + arr[i]);
}
return prefix;
}
function rangeSum(prefix: number[], left: number, right: number): number {
return prefix[right + 1] - prefix[left];
}
Prefix sum + hashmap
Instead of storing every prefix value in an array, keep a hashmap of how many times each running
sum has occurred. At each step, sum - k already seen tells you exactly how many
subarrays ending here sum to k.
Two subarrays sum to 3 here: [1, 2] and [3].
function countSubarraysWithSum(arr: number[], k: number): number {
const seenCount = new Map([[0, 1]]); // empty prefix seen once
let sum = 0;
let count = 0;
for (const value of arr) {
sum += value;
count += seenCount.get(sum - k) ?? 0; // every earlier stop at sum - k is a match
seenCount.set(sum, (seenCount.get(sum) ?? 0) + 1);
}
return count;
}
Where it works — and where it breaks
Prefix sum leans on a quiet assumption: the array doesn't change between queries. That's what makes the O(n) build worth paying once.
Works on a fixed array, many queries
Build once, query forever. Ten queries or ten thousand — each one is still a single subtraction against the same prefix array.
Breaks when the array is mutated
Change one value and every prefix sum from that index onward is now wrong. A plain prefix array needs a full O(n) rebuild after every update — for frequent updates, reach for a Fenwick tree or segment tree instead.