Prefix Sums and Difference Arrays

A prefix sum array stores running totals so that the sum of any contiguous range costs one subtraction. A difference array is its inverse: it turns "add v to every element in a range" into two updates. Together with a hash map, these give O(n) solutions to a huge family of subarray questions, which is why they are among the most frequently tested ideas in interviews.

Intuition

• Prefix sums. Let P[0] = 0 and P[i + 1] = P[i] + a[i], so P[i] is the sum of the first i elements. The sum of a[l..r] (inclusive) is P[r + 1] - P[l]. The extra leading zero removes every special case at the left edge.
• Subarray sums as differences. Every subarray sum is the difference of two prefix sums. "Count subarrays whose sum is k" becomes "count pairs of prefix sums that differ by k", which a hash map of prefix-sum counts answers in one pass. This works with negative numbers, where sliding windows fail.
• 2D prefix sums. S[i][j] is the sum of the rectangle above and to the left of cell (i, j). Inclusion-exclusion builds it and answers any rectangle query in O(1).
• Difference arrays. Store D[i] = a[i] - a[i - 1]. Adding v to a[l..r] only changes D[l] += v and D[r + 1] -= v. After all updates, one prefix sum over D recovers the array. In 2D, a rectangle update touches four corners.

When to use it in interviews / OAs

• Many range-sum queries on an array that does not change (if it changes between queries, use a Fenwick tree or segment tree).
• "Number of subarrays with sum k / sum divisible by k / equal numbers of 0s and 1s / exactly k odd numbers": prefix sums plus a hash map.
• "Longest subarray with sum k": store the first index where each prefix sum appears.
• Rectangle sums in a grid, or counting submatrices with some property.
• Many range increments followed by queries: flight bookings, car pooling capacity, counting how many intervals cover each point.
• Products, XORs and counts work the same way: prefix XOR answers subarray XOR queries, prefix counts answer "how many vowels in s[l..r]".

Template

1D prefix sums

from itertools import accumulate


def build_prefix(nums: list[int]) -> list[int]:
    return [0] + list(accumulate(nums))  # P[i] = sum(nums[:i])


def range_sum(P: list[int], l: int, r: int) -> int:
    """Sum of nums[l..r], both ends inclusive."""
    return P[r + 1] - P[l]

Prefix sums plus a hash map

When the current prefix sum is s, every earlier prefix equal to s - k marks the start of a subarray ending here with sum k. Seed the map with the empty prefix {0: 1}:

from collections import defaultdict


def count_subarrays_with_sum(nums: list[int], k: int) -> int:
    seen: defaultdict[int, int] = defaultdict(int)
    seen[0] = 1  # the empty prefix
    s = total = 0
    for x in nums:
        s += x
        total += seen[s - k]  # subarrays ending here with sum k
        seen[s] += 1
    return total

For divisibility, two prefixes with the same remainder enclose a subarray whose sum is divisible by m. Python's % already returns a non-negative remainder for negative sums:

def count_divisible_subarrays(nums: list[int], m: int) -> int:
    seen: defaultdict[int, int] = defaultdict(int)
    seen[0] = 1
    s = total = 0
    for x in nums:
        s = (s + x) % m
        total += seen[s]
        seen[s] += 1
    return total

2D prefix sums

class MatrixSum:
    def __init__(self, grid: list[list[int]]):
        rows, cols = len(grid), len(grid[0])
        # S[i][j] = sum of grid[0..i-1][0..j-1]; the extra row and column of zeros avoid edge cases
        self.S = [[0] * (cols + 1) for _ in range(rows + 1)]
        for i in range(rows):
            for j in range(cols):
                self.S[i + 1][j + 1] = grid[i][j] + self.S[i][j + 1] + self.S[i + 1][j] - self.S[i][j]

    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:
        """Sum of the rectangle with corners (r1, c1) and (r2, c2), inclusive."""
        S = self.S
        return S[r2 + 1][c2 + 1] - S[r1][c2 + 1] - S[r2 + 1][c1] + S[r1][c1]

Difference arrays

def apply_range_adds(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    """Start from n zeros and apply each (l, r, v): add v to positions l..r inclusive."""
    diff = [0] * (n + 1)  # one extra slot so r + 1 is always a valid index
    for l, r, v in updates:
        diff[l] += v
        diff[r + 1] -= v
    return list(accumulate(diff[:n]))


def apply_rect_adds(rows: int, cols: int, updates: list[tuple[int, int, int, int, int]]) -> list[list[int]]:
    """Each update (r1, c1, r2, c2, v) adds v to a rectangle, corners inclusive."""
    diff = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r1, c1, r2, c2, v in updates:
        diff[r1][c1] += v
        diff[r1][c2 + 1] -= v
        diff[r2 + 1][c1] -= v
        diff[r2 + 1][c2 + 1] += v
    grid = [[0] * cols for _ in range(rows)]
    for i in range(rows):  # a 2D prefix sum of diff recovers the values
        for j in range(cols):
            grid[i][j] = (diff[i][j]
                          + (grid[i - 1][j] if i else 0)
                          + (grid[i][j - 1] if j else 0)
                          - (grid[i - 1][j - 1] if i and j else 0))
    return grid

Complexity

• Building 1D prefix sums: O(n) time and space; each range query O(1).
• Prefix sums plus a hash map: O(n) time, O(n) space.
• 2D prefix sums: O(rows * cols) to build, O(1) per rectangle query.
• Difference arrays: O(1) per update, then O(n) (or O(rows * cols)) to rebuild. Updates must all come before the queries; interleaved updates and queries need a Fenwick tree.

Common pitfalls

• Off-by-one. Use a prefix array of length n + 1 with P[0] = 0, and remember the inclusive query is P[r + 1] - P[l].
• Forgetting seen[0] = 1. Without it, subarrays that start at index 0 are never counted.
• Updating the map too early. In the counting loop, look up s - k before inserting s; otherwise k = 0 counts the empty subarray.
• Using a sliding window with negative numbers. Window sums are not monotonic then; prefix sums with a hash map are the correct tool.
• Negative remainders in C++ and Java: s % m can be negative, so normalize with ((s % m) + m) % m.
• Overflow in fixed-width languages: sums of 10^5 values up to 10^9 need 64-bit integers.
• Inclusion-exclusion signs in 2D: add the full rectangle and the top-left corner, subtract the two strips.

Interview variations

• Range sum query (1D and 2D, immutable): the classes above.
• Subarray sum equals k, subarray sums divisible by k, continuous subarray sum (multiple of k with length at least 2: store the first index of each remainder).
• Contiguous array (equal 0s and 1s): map 0 to -1, then find the longest subarray with sum 0.
• Count nice subarrays (exactly k odd numbers): prefix counts of odd numbers plus a hash map.
• Product of array except self: prefix and suffix products, no division.
• Find pivot index: left sum equals total minus left sum minus the current element.
• Car pooling and corporate flight bookings: difference arrays over stops or flights.
• Number of submatrices that sum to target: fix a pair of rows, compress columns into a 1D array of column sums, and run the hash-map count on it (O(rows^2 * cols)).
• Beyond typical interviews: path sums on trees use root-to-node prefix sums with the lowest common ancestor, and sums over all subsets use a per-dimension prefix sum over bit masks.