Prefix Sums and Difference Arrays

The problem: answering range questions fast

Suppose you have a list of numbers and someone keeps asking, “what is the sum of the values from index l to index r?” The direct answer loops from l to r and adds them up. That works, but each question costs time proportional to the range, so a thousand questions cost a thousand loops.

A prefix sum trades a little upfront work for very cheap answers afterward: precompute the running totals of the list once, and any range sum becomes a single subtraction — O(1) work per question, no matter how wide the range. We measure cost with Big-O notation, which describes how the work grows with the input size n. The pattern here recurs everywhere: spend O(n) to build a summary of cumulative information, then answer each later query in O(1). The same trick powers subarray-sum counting, submatrix sums, and bulk range updates.

Building the prefix sum array

The prefix sum array stores, at each position, the total of everything before it. The one design choice that prevents a swarm of off-by-one bugs is to make the array one longer than the list and start it with a leading 0. Then prefix[i] means “the sum of the first i elements” — indexes 0 through i - 1. So prefix[0] is the sum of zero elements (0) and prefix[len(nums)] is the sum of the whole list.

def build_prefix(nums: list[int]) -> list[int]:
    prefix = [0] * (len(nums) + 1)      # one extra slot; prefix[0] = 0
    for i in range(len(nums)):
        prefix[i + 1] = prefix[i] + nums[i]   # running total
    return prefix

nums = [3, 1, 4, 1, 5, 9]
prefix = build_prefix(nums)
print(prefix)                           # -> [0, 3, 4, 8, 9, 14, 23]

Read the result against the list. prefix[1] is 3 (just the first element), prefix[3] is 8 (3 + 1 + 4), and the final prefix[6] is 23, the sum of all six numbers.

Range sums in O(1)

Now the payoff. The sum of the elements from index l to index r inclusive is prefix[r + 1] - prefix[l]. The larger prefix covers everything up to and including r; the smaller one covers everything before l; the difference is exactly the stretch in between.

def range_sum(prefix: list[int], l: int, r: int) -> int:
    return prefix[r + 1] - prefix[l]    # sum of nums[l..r] inclusive

# prefix was [0, 3, 4, 8, 9, 14, 23] for nums = [3, 1, 4, 1, 5, 9]
print(range_sum(prefix, 1, 3))          # -> 6   (1 + 4 + 1)
print(range_sum(prefix, 0, 5))          # -> 23  (whole list)
print(range_sum(prefix, 2, 2))          # -> 4   (single element)

The off-by-one is worth pinning down, because it is the single most common mistake here. To include the element at r, reach for prefix[r + 1], not prefix[r]. To exclude everything before l, subtract prefix[l], not prefix[l - 1]. The leading 0 makes the l = 0 case work without a special branch: prefix[0] is 0, so a range starting at the front subtracts nothing. In range_sum(prefix, 1, 3) above, prefix[4] - prefix[1] = 9 - 3 = 6 cancels the shared front part (nums[0] = 3) and leaves nums[1] + nums[2] + nums[3].

Subarray sum equals k: prefix sums meet a hash map

A favorite interview question asks: how many contiguous subarrays sum to a target k? The brute-force answer checks every start-and-end pair in O(n²). Prefix sums plus a hash map (a dictionary of value to count) cut it to a single O(n) pass.

The key observation: the subarray from index i to j sums to k exactly when prefix[i] = prefix[j + 1] - k. So as we sweep left to right holding the running prefix sum, the number of subarrays ending here that sum to k is the number of earlier prefix sums equal to running - k. We keep a tally of how often each prefix sum has appeared and look up running - k at every step.

def subarray_sum_count(nums: list[int], k: int) -> int:
    counts = {0: 1}         # one empty prefix with sum 0, seen before we start
    running = 0             # prefix sum of everything up to the current index
    total = 0               # number of matching subarrays found
    for x in nums:
        running += x                        # extend the prefix by one element
        total += counts.get(running - k, 0) # earlier prefixes that close a window summing to k
        counts[running] = counts.get(running, 0) + 1  # record this prefix
    return total

print(subarray_sum_count([1, 2, 3], 3))       # -> 2   ([1,2] and [3])
print(subarray_sum_count([1, 1, 1], 2))       # -> 2   (two overlapping [1,1])
print(subarray_sum_count([3, 4, 7, 2, -3, 1, 4, 2], 7))  # -> 4

Two details make this correct. The map starts as {0: 1} to account for the empty prefix — that is what lets a subarray starting at index 0 be counted (when running itself equals k, we look up 0 and find the seeded entry). And because it counts prefixes rather than remembering positions, it handles negative numbers and overlapping windows for free, which a sliding window cannot.

Trace of subarray_sum_count([1, 2, 3], 3)

At x = 2 the running sum hits 3; we look up 0, find the seeded empty prefix, and count [1, 2]. At x = 3 the running sum is 6; we look up 3, find the prefix recorded one step earlier, and count [3]. Two subarrays, one pass.

Two-dimensional prefix sums

The same idea extends to a grid, so any submatrix sum becomes O(1) after an O(rows·cols) precompute. Build a padded table P where P[i + 1][j + 1] is the sum of the whole rectangle from the top-left corner (0, 0) down to (i, j). Each cell adds the block above and the block to its left, then subtracts their overlap (counted twice) — the inclusion-exclusion pattern.

def build_prefix_2d(grid: list[list[int]]) -> list[list[int]]:
    rows, cols = len(grid), len(grid[0])
    P = [[0] * (cols + 1) for _ in range(rows + 1)]   # padded zero row and column
    for i in range(rows):
        for j in range(cols):
            P[i + 1][j + 1] = (grid[i][j]
                               + P[i][j + 1]      # block above
                               + P[i + 1][j]      # block to the left
                               - P[i][j])         # overlap added twice, subtract once
    return P

def submatrix_sum(P: list[list[int]], r1: int, c1: int, r2: int, c2: int) -> int:
    return (P[r2 + 1][c2 + 1]   # whole rectangle from the origin
            - P[r1][c2 + 1]     # strip above
            - P[r2 + 1][c1]     # strip to the left
            + P[r1][c1])        # corner removed twice, add it back

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
P = build_prefix_2d(grid)
print(submatrix_sum(P, 1, 1, 2, 2))    # -> 28   (5 + 6 + 8 + 9)
print(submatrix_sum(P, 0, 0, 2, 2))    # -> 45   (whole grid)

The query subtracts the strip above and the strip to the left of the target rectangle, which double-removes their shared corner, so we add it back once — the one-dimensional subtraction done along both axes at once.

Difference arrays: many range updates, one pass

Prefix sums answer range questions. The difference array is their mirror image: it applies many range updates cheaply. Suppose you must add a value to every element in a range [l, r], thousands of times over. Applying each update directly is O(range) apiece. Instead, record only the two edges of each update, then run a single prefix pass at the end to realize the final array.

The mechanism: to add val across [l, r], do diff[l] += val and diff[r + 1] -= val. The first entry switches the addition on at l; the second switches it off just past r. A prefix sum over diff then turns those on/off deltas into the actual per-element totals. Each update is O(1); the final realization is one O(n) pass.

def apply_ranges(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    diff = [0] * (n + 1)            # one extra slot so r+1 is always valid
    for l, r, val in updates:
        diff[l] += val             # add val from index l onward
        diff[r + 1] -= val         # cancel it just past r
    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]         # prefix sum turns the deltas into real values
        result[i] = running
    return result

# add 2 over [1,3], add 3 over [2,4], subtract 1 over [0,2]
updates = [(1, 3, 2), (2, 4, 3), (0, 2, -1)]
print(apply_ranges(5, updates))    # -> [-1, 1, 4, 5, 3]

The extra slot at diff[n] keeps diff[r + 1] a valid index even when a range reaches the last element (r = n - 1). This is the go-to pattern for “+1 over every interval” problems, like counting how many meetings overlap at each minute: mark +1 at each start and -1 at each end, then one prefix pass reveals the count everywhere.

A related idea: Kadane’s maximum subarray

Prefix sums are one way to fold cumulative information into a single forward scan. Kadane’s algorithm is a close cousin that solves a different question — the largest sum of any contiguous subarray — while keeping just a running value instead of a whole array. At each element you decide: extend the current run, or start a fresh run right here. Whichever gives the larger sum wins, and you track the best you have ever seen.

def max_subarray(nums: list[int]) -> int:
    best = nums[0]          # best sum seen for any subarray so far
    current = nums[0]       # best sum of a subarray ending at the current index
    for x in nums[1:]:
        current = max(x, current + x)   # extend the run, or start fresh at x
        best = max(best, current)       # remember the best run overall
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # -> 6   ([4, -1, 2, 1])
print(max_subarray([-3, -1, -4]))                       # -> -1  (least-bad single element)
print(max_subarray([5, 4, -1, 7, 8]))                   # -> 23  (whole list)

The tie to prefix sums is worth naming: the maximum subarray ending at j is prefix[j + 1] minus the smallest earlier prefix. Kadane’s tracks that implicitly with the running current, which is why it needs only O(1) space. Both are “one pass over cumulative information,” the throughline of this lesson.

Common pitfalls

• Off-by-one in the range formula. The inclusive range sum is prefix[r + 1] - prefix[l]. prefix[r] - prefix[l] drops the element at r; prefix[r + 1] - prefix[l - 1] breaks when l is 0, since prefix[-1] silently wraps to the last element in Python.
• Forgetting the leading zero. The prefix array must have length n + 1 with prefix[0] = 0; without that empty-prefix slot, ranges starting at index 0 need an awkward special case.
• Seeding the hash map wrong. In subarray-sum-equals-k, start with {0: 1}, not an empty dict — the seed is the empty prefix that lets a subarray beginning at index 0 be counted.
• Difference array index out of range. Size the diff array as n + 1 so diff[r + 1] is valid even when r is the last index.
• Kadane on an all-negative list. Initialize best and current to nums[0], not 0; starting at 0 wrongly reports 0 when the true answer is the least-negative element.

Big-O summary

Practice

1. Write build_prefix and range_sum from scratch, then use them to answer several range queries on [2, -1, 3, -4, 5]. Confirm that the sum over the whole list matches prefix[len(nums)], and that a single-element range range_sum(prefix, i, i) returns nums[i].

2. Extend subarray_sum_count to also handle a list with negatives, such as [1, -1, 1, -1] with k = 0, and explain in one sentence why a sliding window would fail here but the prefix-sum-plus-hash-map approach does not.

3. Use a difference array to solve this: given n = 6 and the flight-booking style updates [(0, 2, 10), (1, 3, 20), (2, 5, 25)], produce the final per-index totals in a single prefix pass, and verify against a brute-force loop that adds each range directly.