Prefix Sum

TL;DR

If a brute force recomputes sum(a[i..j]) for many (i, j) pairs, you’re doing O(n) per query and O(n·q) overall. Precompute one cumulative array — prefix[k] = a[0] + a[1] + … + a[k-1] — and every range sum collapses to one subtraction: sum(i..j) = prefix[j+1] - prefix[i]. Build is O(n), each query is O(1).

Three flavors:

• 1D range sum — answer “sum of a[i..j]?” in O(1) after one O(n) pass.
• Prefix + hash map — count contiguous subarrays whose sum equals k. Walk once, keep a running prefix s, ask “have I seen s - k before?” This is LC 560, Contiguous Array (LC 525), subarray sum divisible by k, and any “subarray with additive property X” problem.
• 2D prefix sum — sub-rectangle sums on a grid via inclusion-exclusion.

Once you internalise that a contiguous subarray’s sum is the difference of two prefix sums, every “count subarrays summing to k” problem becomes two-sum on the prefix array.

The picture in your head

A running tally on a long grocery receipt. After every line item, the register prints a running subtotal. To know what you spent on items 5 through 12, you don’t re-add seven prices — you take the subtotal printed after item 12 and subtract the subtotal printed after item 4. One subtraction, no re-adding, regardless of how long the range is.

That’s the entire pattern. The “receipt” is your prefix array. The “subtotal-after-k” is prefix[k]. The leading zero (prefix[0] = 0) is the receipt header before any item — it’s what makes ranges that start at item 1 work without a special case. The hash-map flavor is the same idea seen sideways: instead of asking “what did I spend on items i through j?” you ask “for how many earlier subtotals would the remaining spend equal exactly $k?”

The problem it solves

The textbook brute force for “sum of a[i..j]” is a loop:

def range_sum_naive(a: list[int], i: int, j: int) -> int:
    s = 0
    for k in range(i, j + 1):
        s += a[k]
    return s

That’s O(n) per query. With q queries it’s O(n·q). At n = 10⁵ and q = 10⁵ you’re looking at 10¹⁰ operations — minutes of CPU time for a single endpoint hit. Any analytics dashboard, any range-aggregation API, any time-series rollup that re-adds the same numbers on every request is paying this cost.

Prefix sum spends one O(n) pass up front to make every subsequent query O(1). The same 10⁵/10⁵ workload becomes 2 · 10⁵ ops — five orders of magnitude faster, with O(n) extra memory. The trade is essentially free whenever the input is immutable or queries vastly outnumber updates.

When to reach for it

Signals that prefix sum is the right move:

• The problem asks for sums (or counts, or XORs) over many ranges of a fixed array.
• A naive solution recomputes the same partial sums repeatedly.
• You need to count or find contiguous subarrays satisfying an additive property — sum equals k, sum divisible by k, equal counts of 0s and 1s, etc. The hash-map variant handles all of these.
• The array is immutable (or queries vastly outnumber updates). If updates are frequent, you want a Fenwick tree or segment tree instead.

Signals it’s not prefix sum: the operation isn’t invertible (max, min — use sparse tables or segment trees), the array changes between queries, or you need the actual elements of the subarray rather than an aggregate.

Flavor 1 — basic range sum

Build a prefix array of length n + 1 with prefix[0] = 0. Then any range sum is one subtraction.

def build_prefix(a: list[int]) -> list[int]:
    prefix = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        prefix[i + 1] = prefix[i] + x
    return prefix

def range_sum(prefix: list[int], i: int, j: int) -> int:
    # inclusive on both ends: a[i] + a[i+1] + … + a[j]
    return prefix[j + 1] - prefix[i]

Worked example. a = [3, 1, 4, 1, 5, 9, 2, 6].

Now answer queries by subtraction:

Verify a[2..5] = 4 + 1 + 5 + 9 = 19. The single-element check a[4..4] = 5 is the off-by-one canary: if your formula returns 0 or 14 for that one, your indexing is wrong.

The reason for the size-n+1 array with prefix[0] = 0: it lets i = 0 work without a special case. sum(0..j) = prefix[j+1] - prefix[0] = prefix[j+1]. Skip the sentinel and you’ll write if i == 0: return prefix[j] everywhere.

Flavor 2 — count subarrays with sum k (hash map)

Same prefix array, but now we want to count contiguous subarrays whose sum equals k. The key observation: a subarray a[i..j] sums to k iff prefix[j+1] - prefix[i] = k, i.e. prefix[i] = prefix[j+1] - k. So as we scan and maintain a running s, we ask “how many earlier prefixes equalled s - k?” — that’s how many valid subarrays end at the current position.

def count_subarrays_sum_k(a: list[int], k: int) -> int:
    freq = {0: 1}     # empty prefix: one way to have sum 0 before we start
    s = 0
    count = 0
    for x in a:
        s += x
        count += freq.get(s - k, 0)
        freq[s] = freq.get(s, 0) + 1
    return count

Worked example. a = [1, 2, 3, -2, 5], k = 3. Expected answer: 4 (subarrays [1,2], [3], [1,2,3,-2,…] no, let’s trace carefully).

Final count = 4. The four subarrays: [1,2] (step 2), [3] (step 3), [2,3,-2] (step 4, prefix went 1→4), and [3,-2,5] (step 5, prefix went 6→9). Each row’s “hits” column is the number of subarrays ending at this index that sum to k — sum those across the run for the total.

The seed freq = {0: 1} is the most-missed line in this template. It encodes “the empty prefix sums to 0,” which is what makes subarrays starting at index 0 countable. Without it, the row at step 2 (s = 3, s - k = 0) returns 0 hits and you undercount by exactly the subarrays anchored at the start.

The same skeleton, with different keys in the map, solves: longest subarray with sum k (store first-seen index instead of frequency), longest subarray with equal 0s and 1s (replace 0 with -1 and look for repeated prefixes), and subarray sum divisible by k (key on s % k).

Flavor 3 — 2D prefix sum

For an m x n grid, P[i][j] = sum of the rectangle from (0,0) to (i-1, j-1) inclusive. Sum of any sub-rectangle becomes inclusion-exclusion on four corners.

def build_2d(grid: list[list[int]]) -> list[list[int]]:
    m, n = len(grid), len(grid[0])
    P = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            P[i+1][j+1] = grid[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
    return P

def rect_sum(P, r1, c1, r2, c2):  # inclusive corners
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Worked example. Grid:

Built P (size 4x4, with a zero row and zero column on top/left):

Query: sum of the bottom-right 2x2 sub-rectangle (r1,c1)=(1,1), (r2,c2)=(2,2). Expected: 5 + 6 + 8 + 9 = 28.

Formula: P[3][3] - P[1][3] - P[3][1] + P[1][1] = 45 - 6 - 12 + 1 = 28. The + P[1][1] term adds back the top-left rectangle that got subtracted twice — that’s the inclusion-exclusion correction.

Why it works — the invariant

For 1D, the invariant is prefix[k] = a[0] + a[1] + … + a[k-1], with prefix[0] = 0. Telescoping gives prefix[j+1] - prefix[i] = a[i] + a[i+1] + … + a[j] exactly — every range sum is a difference of two scalars you already computed.

For the hash-map flavor, the invariant is: at index j, the running prefix is s = prefix[j+1], and for every earlier index i with prefix[i] = s - k, the subarray a[i..j] sums to k. The frequency map counts those i in O(1). It’s two-sum on the prefix array.

For 2D, the invariant generalises by inclusion-exclusion: the sum of the rectangle anchored at (0,0) with corners at (i, j) decomposes into the union of three smaller rectangles minus their double-counted intersection.

Complexity & memory tradeoffs

Prefix sum’s edge over a hash-map approach for plain range sums is memory: both are O(n), but the prefix array is a contiguous block (cache-friendly, SIMD-vectorisable), while a hash map pays per-bucket overhead and random memory access. The hash-map flavor (LC 560) is a different tool — it’s the only O(n) option for counting subarrays with a target sum when the array contains negatives, because sliding window needs monotonicity that negatives break.

Common pitfalls

• Inclusive vs exclusive ranges. Decide once: prefix has length n+1, prefix[0] = 0, and sum(i..j) (both inclusive) is prefix[j+1] - prefix[i]. Mixing this with a length-n prefix and per-call special cases is where every off-by-one comes from.
• Forgetting freq = {0: 1} in the hash-map flavor. Without it, every subarray that starts at index 0 is invisible. If your LC 560 answer is exactly N too low (where N = subarrays from index 0 summing to k), this is why.
• Updating the freq map before the lookup. Order matters: query freq[s - k] first, then increment freq[s]. Swap them and you’ll falsely count the empty subarray a[i..i-1] when k = 0.
• Integer overflow on large arrays. A million 32-bit ints summing to a 64-bit prefix is fine in Python but blows up in C++/Java with int. Default to int64 / long for prefix arrays in production code.
• 2D inclusion-exclusion sign error. It’s P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]. The + on the last term is the part people forget — without it you double-subtract the top-left corner.

Where you see this in production

The pattern is everywhere once you know to look for it:

• pandas Series.cumsum and NumPy np.cumulative_sum. Vectorised prefix-sum builds. Anything in pandas that computes a rolling total or expanding window sits on top of cumsum, and the C implementation is the identical prefix[i+1] = prefix[i] + x loop.
• PostgreSQL window functions. SUM(x) OVER (ORDER BY t ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) is literally a prefix sum, and the planner often materialises it once and reuses it for sibling window expressions. Range frames (BETWEEN n PRECEDING AND CURRENT) become prefix[j+1] - prefix[i] under the hood.
• Prometheus rate() and increase(). Prometheus stores monotonically increasing counters; rate() over a window is the prefix-sum difference-of-endpoints trick applied to a time series, divided by the window length. The whole counter abstraction exists because differences of prefixes are cheap and reliable.
• CDN log analytics (Cloudflare, Fastly). “Bytes served per region per hour” is a prefix-sum over a sorted log stream; arbitrary (start, end, region) queries reduce to two lookups in a precomputed cumulative table. The 2D variant powers heatmap dashboards.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.