Prefix Sums: The Core Idea

A shop keeps one line per day in its sales book: the day, and what it sold. Every week the owner asks questions like "how much did we sell from day 12 to day 40?" Adding 29 numbers by hand is slow, and next week the owner asks about day 13 to day 41, which repeats 28 of those additions.

A smarter bookkeeper adds one more column: the running total since the book was opened. Now "day 12 to day 40" is the running total at day 40 minus the running total at day 11. One subtraction, no matter how long the range is. That extra column is a prefix sum array, and this whole section is built on it.

Put numbers on the slow way. An array of 100,000 elements and 100,000 queries, each covering about half the array, means 100,000 × 50,000 = 5 × 10⁹ additions. Python manages roughly 10⁷ simple operations per second, so that runs for minutes. With a running-total column it is 100,000 additions to build and 100,000 subtractions to answer.

The picture: distance markers on a road

The picture tells you what the pattern needs. First, the underlying data must not change between questions — if someone moves a road marker, every marker after it is wrong. Second, the operation must be "undoable": you can subtract a sum away. You cannot "subtract" a minimum, which is why range-minimum queries need a different tool.

How to recognise it

Interviewers rarely say "use prefix sums". They describe the situation, and the situation has a few fixed shapes.

• Many range questions on a fixed array. "Answer Q queries of the form: sum of elements from i to j." The words immutable, fixed or up to 10⁵ queries all mean "precompute once".
• Counting or measuring contiguous subarrays by their sum. "How many subarrays sum to K?", "longest subarray whose sum is 0", "subarrays whose sum is divisible by K".
• A property that becomes a sum after a small change. "Equal number of 0s and 1s" becomes "sum is 0" once every 0 is counted as −1.
• Negative numbers are allowed. This is the constraint that separates prefix sums from a sliding window. A window only works when growing it always raises the sum; negatives break that, and prefix sums do not care.
• n up to 10⁵ with a "subarray" question. There are about n²/2 = 5 × 10⁹ subarrays, so checking each one is out. You need O(n) or O(n log n).

Two words stop it applying. If the problem lets you pick elements from anywhere (a subsequence or a subset), this is usually hashing or dynamic programming. If the array is updated between queries, a plain prefix array goes stale; you need a Fenwick tree, covered in the first problem lesson's follow-ups.

How it works

Take nums = [3, 1, 4, 1, 5, 9]. Define prefix[k] as the sum of the first k elements — not "up to index k". So prefix[0] is the sum of zero elements, which is 0, and the array has n + 1 entries.

So prefix = [0, 3, 4, 8, 9, 14, 23].

Now ask for the sum of indices 2 to 4: 4 + 1 + 5 = 10. prefix[5] is the first five elements (indices 0 to 4) = 14. prefix[2] is the first two elements (indices 0 and 1) = 4. The first five minus the first two leaves exactly indices 2, 3 and 4: 14 − 4 = 10.

That sentence gives the rule. Do not memorise it; derive it each time:

sum(nums[i..j], both ends included) = prefix[j + 1] - prefix[i]

prefix[j + 1] is "everything up to and including j". prefix[i] is "everything before i". The difference is the range.

The same equation, read backwards, drives the harder problems. If a subarray from i to j sums to k, then prefix[j + 1] - prefix[i] = k, so prefix[i] = prefix[j + 1] - k. Walk the array once, keep the running total, and at each position ask: how many earlier running totals equal "running − k"? A hash map answers that in O(1). This is the invariant behind Subarray Sum Equals K, Contiguous Array and every counting problem in this section: the map holds exactly the prefixes that end before the current position.

Variants

The pattern takes a handful of forms. Each problem lesson in this section is one row of this table.

The question behind every row is the same: does this operation have an inverse? Sums undo with subtraction. XOR undoes itself, because a ^ a = 0 (the bit manipulation section explains why). Products would undo with division, but division breaks on zero, which is why Product of Array Except Self combines a left pass and a right pass instead.

The difference array is the pattern run backwards. When you need many "add v to every index from l to r" updates and only one read at the end, store the changes, then take one prefix sum:

1def apply_range_adds(n: int, updates: list[tuple[int, int, int]]) -> list[int]:2    """Apply 'add v to every index in [l, r]' updates, then read the array once."""3    diff = [0] * (n + 1)              # one spare slot so r + 1 never overflows4    for l, r, v in updates:5        diff[l] += v                  # start adding v at l6        diff[r + 1] -= v              # stop adding it after r7    result, running = [], 08    for i in range(n):9        running += diff[i]            # a prefix sum of diff rebuilds the array10        result.append(running)11    return result

For n = 5 with updates "add 2 to [1, 3]" and "add 5 to [0, 1]", diff becomes [5, 2, -5, 0, -2, 0] and the result is [5, 7, 2, 2, 0]. Index 1 received both updates: 5 + 2 = 7. A thousand updates over a million elements cost about 1,000 + 1,000,000 steps instead of up to 10⁹.

The templates

Template 1 — range queries.

1def build_prefix(nums: list[int]) -> list[int]:2    """Return prefix where prefix[k] is the sum of the first k elements."""3    prefix = [0] * (len(nums) + 1)4    for k, value in enumerate(nums):5        prefix[k + 1] = prefix[k] + value6    return prefix789def range_sum(prefix: list[int], i: int, j: int) -> int:10    """Sum of nums[i..j], both ends inclusive."""11    return prefix[j + 1] - prefix[i]

Line by line:

• [0] * (len(nums) + 1) makes one extra slot. prefix[0] = 0 is a real entry — the sum of nothing — not a placeholder.
• prefix[k + 1] = prefix[k] + value reads as "the first k + 1 elements are the first k, plus the next one". That sentence is the whole build.
• prefix[j + 1] - prefix[i] needs no if i == 0 branch, because prefix[0] exists and is 0.

The alternative — a length-n array where prefix[k] includes index k — forces a special case on every query (if i == 0: return prefix[j]). That branch is where bugs live. Adding a boundary element instead of a branch is the same instinct as a dummy head in a linked list.

Template 2 — prefix plus hash map.

1def count_ranges_with_sum(nums: list[int], k: int) -> int:2    """Count contiguous subarrays whose sum is exactly k."""3    seen = {0: 1}                    # the empty prefix, before index 04    running = count = 05    for value in nums:6        running += value7        count += seen.get(running - k, 0)   # earlier prefixes that fit8        seen[running] = seen.get(running, 0) + 19    return count

• seen = {0: 1} records the empty prefix. Without it, a subarray that starts at index 0 is never counted.
• running is the prefix sum up to and including the current element. It replaces the whole prefix array, because we only ever look backwards.
• The lookup happens before the current prefix is stored. So the map only holds prefixes that end strictly before this element, which means every match is a real, non-empty subarray.
• For "longest" questions, store the first index of each prefix instead of a count, seeded {0: -1}. For "divisible by k", store remainders.

Complexity

Template 1 costs O(n) time and O(n) space to build, then O(1) per query. Q queries cost O(n + Q) in total, against O(n × Q) for the loop-per-query version.

Template 2 costs O(n) time: one pass, and each map operation is O(1) on average. Space is O(n) for the map in the worst case, when every prefix is different. When the keys are remainders mod k, the map has at most k keys, so space is O(k).

The 2D version costs O(rows × cols) to build and O(1) per rectangle query. The difference array costs O(1) per update and O(n) for the final read.

Where it goes wrong

1. Mixing prefix indices and array indices. Writing prefix[j] - prefix[i] when you meant prefix[j + 1] - prefix[i] gives answers that are right in the middle and wrong at the edges, or an IndexError on the last element. The five-second test: query a single element, i = j. For [3, 1, 4, 1, 5, 9], the sum of 3..3 must be prefix[4] - prefix[3] = 9 - 8 = 1. If you get 0 or 8, one offset is wrong.

2. Forgetting the seed. Without {0: 1} (counting) or {0: -1} (longest), every subarray that starts at index 0 is missed. The code still returns a plausible number, so the bug survives a quick look.

3. Using a prefix array on data that changes. A prefix array is a snapshot. Change nums[2] and every entry from prefix[3] onwards is stale. Rebuilding costs O(n) per update, so n updates and n queries cost O(n²). The right tool is a Fenwick tree or segment tree, with O(log n) for both.

4. Assuming the prefix array is sorted. It is only sorted when every element is non-negative. With negatives, you cannot binary-search it and you cannot use a sliding window on the original array.

5. Overflow outside Python. Python integers never overflow. In Java or C++, 10⁴ elements of size 10⁹ sum to 10¹³, far past the 32-bit limit of about 2.1 × 10⁹. Use a 64-bit type for the prefix even when the inputs fit in 32 bits, and say so out loud.