Prefix Sums & Difference Arrays

A prefix sum is a small precomputation that changes the shape of a problem. If you will ask many questions about sums of contiguous ranges, do the addition once up front and turn each later query into subtraction.

Difference arrays are the inverse trick. If many operations add a value across a range, mark only where the range starts and stops, then rebuild the final array with one prefix pass.

Both patterns are the same idea: store cumulative change so repeated range work becomes O(1) per query or update.

The mental model

Build prefix one slot longer than the input. prefix[i] means “sum of the first i elements,” so prefix[0] is 0 and the sum from index left through right is the total before right + 1 minus the total before left.

def build_prefix(nums):
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    return prefix

def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

That one extra leading zero removes most boundary bugs.

For range updates, use a difference array:

def apply_updates(n, updates):
    diff = [0] * (n + 1)
    for left, right, delta in updates:
        diff[left] += delta
        diff[right + 1] -= delta

    nums = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        nums[i] = running
    return nums

Each update marks “start adding here” and “stop adding after right.” The final prefix pass applies all active deltas.

For a grid, a 2D prefix sum stores the sum of the rectangle from (0, 0) to each cell. A query rectangle uses inclusion-exclusion: big rectangle minus the strip above and the strip left, plus the corner you subtracted twice.

Pattern recognition

Variations

Worked problems

All three problems are about refusing to re-add the same range again.

class NumArray:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1

    prefix = 0
    total = 0
    for x in nums:
        prefix += x
        total += seen[prefix - k]
        seen[prefix] += 1

    return total

def get_modified_array(n, updates):
    diff = [0] * (n + 1)

    for start, end, inc in updates:
        diff[start] += inc
        diff[end + 1] -= inc

    ans = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        ans[i] = running

    return ans

When not to use it

Also watch the update/query mix. A plain prefix array is great for immutable data. If the underlying values change between queries, rebuilding the whole prefix array after every update throws away the benefit.