Prefix Sums & Difference Arrays

Range sums in O(1), counting subarrays with a hash map, and batched range updates.

A prefix sum array stores the running total, so the sum of any subarray becomes a single subtraction. With a hash map added, it solves "count the subarrays whose sum is k" in O(n), even when the array has negative numbers and sliding window can't be used.

The basic idea

prefix[i] is the sum of the first i elements, so prefix[0] = 0. Then:

sum(nums[l..r]) = prefix[r + 1] - prefix[l]

from itertools import accumulate

class RangeSum:
    def __init__(self, nums):
        self.prefix = [0, *accumulate(nums)]

    def query(self, l, r):            # inclusive
        return self.prefix[r + 1] - self.prefix[l]

The leading 0 is what makes ranges that start at index 0 work without a special case.

Prefix sum + hash map

A subarray nums[i..j] sums to k exactly when prefix[j+1] - prefix[i] == k. So as you scan, ask "how many earlier prefixes equal current - k?"

from collections import Counter

def subarray_sum(nums, k):
    seen = Counter({0: 1})       # the empty prefix
    total = count = 0
    for x in nums:
        total += x
        count += seen[total - k]
        seen[total] += 1
    return count

Variations of the same idea:

[!INTERVIEW] Why not sliding window? Sliding window needs the window sum to change monotonically, which only holds when every value is non-negative. Say this when you choose prefix sums: "There are negative numbers, so shrinking the window doesn't reliably decrease the sum. I'll use a prefix sum with a hash map instead."

Difference arrays: many range updates

The inverse trick: to add v to every element in [l, r] many times, record diff[l] += v and diff[r + 1] -= v. After all the updates, one prefix-sum pass recovers the final array. That's O(1) per update instead of O(r − l).

def flight_bookings(bookings, n):
    diff = [0] * (n + 1)
    for first, last, seats in bookings:      # 1-indexed, inclusive
        diff[first - 1] += seats
        diff[last] -= seats
    return list(accumulate(diff[:n]))

The same idea answers "how many meetings overlap at the busiest moment?" (+1 at each start, −1 at each end, take the maximum running sum) and car pooling capacity checks.

2D prefix sums

For rectangle sums in a matrix, P[r][c] holds the sum of everything above and to the left. A query uses inclusion–exclusion:

P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Prefix products and other running aggregates

Running values aren't limited to sums:

Product of the array except self: multiply a prefix product from the left by a suffix product from the right. No division needed.
Prefix XOR: XOR over a range = px[r+1] ^ px[l].
Prefix maximum and suffix maximum: "Trapping Rain Water" needs the tallest bar to the left and to the right of every index.

[!TIP] Practice Range Sum Query · Subarray Sum Equals K · Continuous Subarray Sum · Contiguous Array · Product Except Self · Corporate Flight Bookings · Range Sum Query 2D · Find Pivot Index