Lesson 14 · Intermediate

Prefix sums — range queries in O(1)

📖 Walk me through it — plain English

A prefix sum is just the running total of an array as you walk left to right. After reading the first few numbers, the prefix sum is everything you've added so far. The key trick: the sum of any slice of the array (a "subarray" — a run of neighboring elements) equals the prefix sum at its end minus the prefix sum just before its start. So if you remember every prefix sum you've seen, you can answer "what's the sum from here to there?" in one subtraction instead of re-adding the whole slice.

This lesson solves "how many subarrays add up exactly to k?". The clever part is rearranging that subtraction. We want end_sum − start_sum = k. Flip it: start_sum = end_sum − k. So at each position, while the running total cur is the current end_sum, we ask: "how many earlier prefix sums equalled cur − k?" Each one marks a slice that sums to k. We keep those counts in a hash map (a dictionary that gives instant lookup by key) called counts, mapping each prefix-sum value to how many times we've seen it.

Analogy: imagine walking a trail with mile-markers showing your total distance so far (0, 1, 3, 6...). To find every stretch of trail that's exactly 3 miles long, you don't re-measure each stretch. At your current marker you just check: "is there a past marker reading exactly (here − 3)?" Every matching past marker is the start of a 3-mile stretch. The notebook of markers you've passed is the hash map.

We seed the map with {0: 1} — an "empty prefix" of sum 0 that we've conceptually seen once. That handles slices starting at the very beginning of the array. Let's trace nums = [1, 2, 3], k = 3 (the answer should be 2: the slices [1,2] and [3]).

Start · cur (running total) = 0, ans = 0. Map seeded with {0:1}. We sweep the array left to right.

Step 1 · read 1. cur becomes 0+1 = 1. Look for cur−k = 1−3 = −2 in the map → not there, so add 0 to ans (still 0). Then record this prefix: map = {0:1, 1:1}.

Step 2 · read 2. cur becomes 1+2 = 3. Look for cur−k = 3−3 = 0 → the map has 0 once, so ans += 1 (ans = 1). That match is the empty prefix, meaning the slice [1,2] from the start sums to 3. Record: map = {0:1, 1:1, 3:1}.

Step 3 · read 3. cur becomes 3+3 = 6. Look for cur−k = 6−3 = 3 → the map has 3 once, so ans += 1 (ans = 2). That earlier prefix of 3 was right before this element, so the slice [3] alone sums to 3. Record: map = {0:1, 1:1, 3:1, 6:1}.

Done · the loop ends and we return ans = 2 — exactly the two slices [1,2] and [3] that sum to 3.

Why it's fast: we touch each element once, and every hash-map lookup and insert is roughly constant time, so the whole thing is O(n) time (work grows in step with the array length) using O(n) extra space for the map. A naive approach would re-sum every possible slice — checking all start/end pairs — which is O(n²). The order of the two map operations matters: we look up cur − k before recording the current cur, so a single element can't accidentally match itself as a zero-length slice.

Combines lethally with hash maps: "subarrays with sum = k" is prefix + map, single pass.

The core idea: precompute once, answer forever

Here is the plain-English on-ramp. Suppose you have an array of numbers and people keep asking you "what's the total of elements from index i to index j?" — a range-sum query (a question of the form "add up this contiguous stretch of the array"). The lazy answer is to re-add the stretch every time, which costs work proportional to its length. If a thousand queries come in, you re-add a thousand times. Wasteful.

The prefix-sum idea is: do the adding once, up front, and store the running totals. After that one-time setup, every range query becomes a single subtraction — O(1) (constant time, independent of how long the range is). You pay O(n) once to build the table, then answer any number of queries almost for free. That "precompute once, query cheaply" pattern is the whole lesson.

Vocabulary, defined inline

Prefix sum (a.k.a. cumulative sum). The total of all elements up to a given position. "Prefix" means "a beginning chunk" — the prefix of length 3 is the first 3 elements. "Cumulative" just means "accumulated so far." Both names point at the same running total.
Prefix-sum array P. An array that stores those running totals, one per cut-point. We define P[0] = 0 (the empty prefix — nothing added yet) and P[k] = nums[0] + nums[1] + … + nums[k−1] (the sum of the first k elements). Note P has length n+1 for an array of n numbers, because there are n+1 places to "cut" (before everything, after each element).
Subarray / slice. A run of neighboring elements, e.g. nums[i..j]. Contiguous — no gaps. (Different from a subsequence, which may skip around.)
Range-sum query. The question "what is the sum of nums[i..j]?" Prefix sums answer it in one subtraction.
Difference array. The mirror-image tool, covered below: instead of reading range sums fast, it lets you add a constant to a whole range fast.

The formula: `P[j] − P[i]`, and why the off-by-one works

The single fact to internalise: the sum of a range equals the prefix at its end minus the prefix just before its start. With the exclusive-right convention above (P[k] = sum of the first k elements, not including index k itself):

Sum of nums[i..j] inclusive on both ends = P[j+1] − P[i].

Why does the indexing line up? P[j+1] is "everything up to and including index j" — because P counts the first j+1 elements, which are indices 0…j. P[i] is "everything strictly before index i" — the first i elements, indices 0…i−1. Subtract the second from the first and every element below i cancels, leaving exactly nums[i] + … + nums[j]. The reason i is not shifted but j is comes straight from the convention: P is exclusive on the right, so the start index i already points at the right cut, while the end index needs the +1 to include nums[j]. If you instead define P inclusive, the off-by-ones move; pick one convention and stay with it.

Sanity check the endpoints. The sum of the whole array is P[n] − P[0] = P[n] − 0 = P[n] ✓. The sum of a single element nums[i] is P[i+1] − P[i] ✓. The sum of an empty range is P[i] − P[i] = 0 ✓. When in doubt, test these three.

Traced example: build the table, answer two queries

Take nums = [4, 2, 7, 1, 5] (so n = 5). Build P left to right, each entry being the previous entry plus the next element:

# nums =        4    2    7    1    5
# P[0] = 0                       (empty prefix)
# P[1] = P[0] + 4  = 0 + 4  = 4
# P[2] = P[1] + 2  = 4 + 2  = 6
# P[3] = P[2] + 7  = 6 + 7  = 13
# P[4] = P[3] + 1  = 13 + 1 = 14
# P[5] = P[4] + 5  = 14 + 5 = 19
# P =           [0,  4,  6,  13,  14,  19]   (length n+1 = 6)

Query 1 — sum of nums[1..3] (the elements 2, 7, 1, which clearly total 10). Apply P[j+1] − P[i] with i = 1, j = 3: that's P[3+1] − P[1] = P[4] − P[1] = 14 − 4 = 10 ✓. One subtraction, no re-adding.

Query 2 — sum of nums[0..4] (the whole array, 4+2+7+1+5 = 19). With i = 0, j = 4: P[4+1] − P[0] = P[5] − P[0] = 19 − 0 = 19 ✓. Notice how the seeded P[0] = 0 is exactly what makes a range that starts at index 0 come out right — the same role the {0: 1} seed plays in the hash-map version above.

Recognition signals & pitfalls

Reach for prefix sums when the problem statement says any of these out loud:

"Sum of a subarray" / "sum of a contiguous range" — the textbook trigger.
"Many range queries" against a fixed array — build once, answer each in O(1).
"Count / find subarrays with sum = k" (or sum divisible by k, or sum in a range) — prefix sum + a hash map, as in the template below.
"Running total" / "running sum" / "cumulative" anything.
Range updates ("add v to every element in [l, r]") rather than reads — that's the difference-array variant.

And the pitfalls that quietly cost correctness:

Inclusive vs. exclusive bounds. The number-one bug. Decide whether your P is exclusive-right (sum of first k) or inclusive, then derive the formula once and test the three endpoint cases above. Mixing conventions mid-problem produces silent off-by-one errors.
Forgetting P[0] = 0 (or the {0:1} map seed). Without the empty prefix, every range that starts at index 0 is wrong.
Lookup-before-insert order in the hash-map version. Record the current prefix after the lookup, or an element can match itself.
Stale table. Prefix sums assume the array doesn't change. If single elements get updated between queries, rebuilding is O(n) each time — that's when a Fenwick/segment tree earns its keep (out of scope here).
Overflow in fixed-width languages: running totals can exceed 32-bit range even when individual elements are small. Use a wide enough integer type.

Two cousins: 2-D prefix sums and difference arrays

2-D prefix sums extend the idea to a grid so you can total any rectangle in O(1). Define P[r][c] = the sum of the whole sub-rectangle from the top-left corner down to row r−1, column c−1. The sum of the rectangle with corners (r1,c1) top-left and (r2,c2) bottom-right is then inclusion–exclusion: take the big block, subtract the strip above it and the strip to its left, and add back the top-left corner you subtracted twice — P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]. Same precompute-once, query-O(1) bargain, one dimension up.

Difference arrays are prefix sums run backwards. Where a prefix sum turns an array of values into an array of running totals, a difference array turns an array of values into an array of step changes: D[i] = nums[i] − nums[i−1]. The payoff: to add a constant v to an entire range [l, r], you don't touch every element — you just do D[l] += v and D[r+1] −= v, two writes regardless of range length. After all such range-updates are queued, taking the prefix sum of D reconstructs the final array in one O(n) pass. So: prefix sum = fast range reads; difference array = fast range writes. They're inverses of each other.

Template — Subarray Sum Equals K

def subarray_sum(nums, k):
    counts = {0: 1}     # empty prefix counts once
    cur = ans = 0
    for v in nums:
        cur += v
        ans += counts.get(cur - k, 0)
        counts[cur] = counts.get(cur, 0) + 1
    return ans

function subarraySum(nums: number[], k: number): number {
  const counts = new Map<number,number>([[0, 1]]);
  let cur=0, ans=0;
  for (const v of nums) {
    cur += v;
    ans += counts.get(cur - k) ?? 0;
    counts.set(cur, (counts.get(cur) ?? 0) + 1);
  }
  return ans;
}

Read the template line by line against the trace above. counts is the hash map of "prefix-sum value → how many times seen," seeded with the empty prefix. cur is the live running total (the current end_sum). Each loop iteration: extend cur, ask how many earlier prefixes equalled cur − k (each is the start of a valid slice), then record cur for future iterations to find. The whole thing is one pass — O(n) time, O(n) space.

SoloMock: Product of Array Except Self (prefix/suffix product variant)

Build the prefix-sum array yourself — run it live:

Go deeper (optional): for arrays that change between queries, a Fenwick tree (binary indexed tree) or segment tree keeps both updates and range sums at O(log n) — search "Fenwick tree range sum" once you're comfortable with the static prefix-sum table here.

Takeaway: a prefix sum is a precomputed running total; build P once in O(n), then any range sum is P[j+1] − P[i] in O(1). Seed the empty prefix (P[0] = 0 or {0:1}), pick one inclusive/exclusive convention and test the endpoints, and pair prefix sums with a hash map to count "subarrays with sum = k" in a single O(n) pass. The grid version totals rectangles by inclusion–exclusion; the difference-array mirror image makes range writes O(1).

→ Going deeper: Prefix sums often feed sliding-window max/min problems. See Sliding window.

→ Going deeper: Prefix sums are the simplest dynamic-programming table. See DP — 1-D sequences.