Prefix sums and products

Problem

Questions about contiguous ranges of an array ("sum from index i to j", "how many subarrays add up to k") are slow if every query re-adds its range: O(n) per query, O(n²) over many queries. Prefix sums remove the repeated addition: totals are computed once, and every range becomes the difference of two stored totals.

Intuition

Think of a car's odometer. To know how far you drove between two stops you do not retrace the trip: you read the odometer at each stop and subtract. A prefix-sum array is the odometer reading after every element. Any distance between two readings is a subtraction, however long the stretch.

The same picture explains the hash-map version. A stretch sums to k when the odometer at its end is k more than at its start. So while driving, at each point ask: "how many earlier readings are exactly k below where I am now?" That is a dictionary lookup, and each such earlier reading is the start of one qualifying stretch.

The extra leading zero removes the special case for ranges that start at index 0.

Mechanics

The invariant

Define prefix[0] = 0 and prefix[i] = prefix[i − 1] + nums[i − 1]. By induction, prefix[i] is the sum of the first i elements. For a range nums[l..r] inclusive, prefix[r + 1] − prefix[l] is the sum of the first r + 1 elements minus the sum of the first l elements, which leaves exactly elements l to r. The leading zero is what makes l = 0 work without a branch.

Prefix sums with a hash map

To count subarrays with sum k, you cannot precompute and query; the question is about all ranges at once. Walk the array keeping the running sum s. A subarray ending here starts after some earlier point whose prefix equals s − k. So add to the answer the number of earlier prefix values equal to s − k, then record s. Seed the map with {0: 1}, the empty prefix, so subarrays starting at index 0 count. Negative numbers are fine, because nothing relies on the prefix being monotonic (this is why a sliding window fails here).

Products without division

The product of all elements except nums[i] is (product of nums[0..i−1]) × (product of nums[i+1..n−1]). Compute the left products in one pass and the right products in a second pass. Division would fail on zeros and is usually forbidden. The right pass can multiply into the output array in place, so the extra space is O(1) beyond the answer.

Two dimensions

Let table[r][c] be the sum of the sub-grid with rows before r and columns before c. Building it uses inclusion and exclusion: a cell's table entry is the cell plus the entry above plus the entry on the left, minus the entry diagonally above-left that both of them counted. A rectangle then costs four lookups: take the big corner, subtract the strip above and the strip to the left, and add back the overlap that was subtracted twice.

Four lookups whatever the size of the rectangle.

Worked example

Range queries. On [3, 1, 4, 1, 5, 9, 2, 6] the prefix array is [0, 3, 4, 8, 9, 14, 23, 25, 31]. Each query below is two lookups and one subtraction.

Counting subarrays with sum 7 in [3, 4, 7, 2, -3, 1, 4, 2] with the map of earlier prefix sums. At each element, need is the running sum minus 7, and earlier is how many times that value appeared among earlier prefix sums (the empty prefix 0 included).

There are 4 such subarrays: [3, 4], [7], [7, 2, −3, 1] and [1, 4, 2]. The run made 8 map lookups; checking all ranges would take 36.

Bar height is the running sum; green bars end at least one subarray summing to 7.

Products. For [1, 2, 3, 4]: left products [1, 1, 2, 6], right products [24, 12, 4, 1], so each position is their product: [24, 12, 8, 6].

Implementation

from itertools import accumulate


class RangeSum:                                 # immutable array, many queries
    def __init__(self, nums):
        self.prefix = [0, *accumulate(nums)]

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


def count_subarrays_with_sum(nums, k):          # works with negatives
    seen = {0: 1}                               # the empty prefix
    running = total = 0
    for x in nums:
        running += x
        total += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return total


def product_except_self(nums):
    out = [1] * len(nums)
    for i in range(1, len(nums)):               # out[i] = product of everything left of i
        out[i] = out[i - 1] * nums[i - 1]
    right = 1
    for i in range(len(nums) - 1, -1, -1):      # fold in the product of everything right of i
        out[i] *= right
        right *= nums[i]
    return out


class RangeSum2D:
    def __init__(self, grid):
        rows, cols = len(grid), len(grid[0])
        self.t = [[0] * (cols + 1) for _ in range(rows + 1)]
        for r in range(rows):
            for c in range(cols):
                self.t[r + 1][c + 1] = (grid[r][c] + self.t[r][c + 1]
                                        + self.t[r + 1][c] - self.t[r][c])

    def query(self, r1, c1, r2, c2):
        t = self.t
        return t[r2 + 1][c2 + 1] - t[r1][c2 + 1] - t[r2 + 1][c1] + t[r1][c1]

Variations and edge cases

• Longest subarray with a property. Store the first index at which each prefix value appeared; when the value appears again, the stretch between has the property and its length is the difference of indices. Balanced 0/1 arrays use this with 0 mapped to −1.
• Divisibility. To count subarrays whose sum is divisible by k, count prefix sums by sum % k; two equal remainders bracket a multiple of k. (Python's modulo is never negative, which helps.)
• Trees. Running sums along a root-to-node path work the same way, but the map must be undone when the DFS leaves a node so sibling branches do not see it.
• Weighted random pick. The prefix array is sorted, so bisect_left(prefix, random_point) chooses the slice containing the point.
• Updates. If the array changes between queries, a prefix array costs O(n) per update; use a Fenwick or segment tree instead.
• Edge cases: forgetting the leading zero (and the {0: 1} seed), off-by-one on inclusive ranges, recording the running sum before looking up (double counts when k = 0), integer overflow in other languages, and zeros in the array if you try division.

Complexity and tradeoffs

• Time: O(n) to build, O(1) per range query. The map version is O(n) total. The 2D table is O(rows × cols) to build and O(1) per rectangle.
• Space: O(n) for the table (or O(distinct prefixes) for the map version). The product trick is O(1) extra beyond the output.
• Baselines. Re-adding each range is O(n) per query. For only one query, a plain loop is as good and uses no extra memory. A sliding window solves "sum equals k" in O(1) space but only when all values are non-negative.
• When it fails. Mutable arrays (use a Fenwick tree), operations that are not invertible, like max or min (use a sparse table or segment tree), and products with zeros when you want to divide.

Problems

The home problems cover the three flavors: precomputed products and rectangles, running-sum maps for counting and balancing, and prefix sums as a lookup structure (weighted random, jump windows). The "also uses" list shows prefix totals inside windows, sweep lines and the trapped-water problem.

Medium

• 238. Product of Array Except Self Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The answer at i is the product of everything to its left times everything to its right, computed in two passes without division.
• 304. Range Sum Query 2D - Immutable NeetCode 250
  Precompute 2D prefix sums once, then every rectangle's sum is four lookups combined by inclusion and exclusion.
• 437. Path Sum III Grind 169
  Count running sums along the current root-to-node path in a map, and look up how many earlier sums differ from the current one by the target.
• 525. Contiguous Array Grind 169
  Count 0 as -1, and then any two equal running sums mark a subarray with equal 0s and 1s.
• 528. Random Pick with Weight Grind 169
  Build prefix sums of the weights and binary-search a random point in the total to find which index's slice it lands in.
• 560. Subarray Sum Equals K Grind 169 NeetCode 250
  Count earlier running sums in a map, because a subarray sums to k exactly when two running sums differ by k.
• 1871. Jump Game VII NeetCode 250
  Count how many reachable indices lie in the window [i - maxJump, i - minJump], with a sliding count or a running prefix sum.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 209. Minimum Size Subarray Sum Medium
• 1094. Car Pooling Medium
• 42. Trapping Rain Water Hard

Connections

The hash-map flavor is the complement-map idea from the hash maps page applied to running totals. Fenwick and segment trees keep prefix sums fast under updates. Sweep lines are prefix sums over events, and 2D prefix sums reappear in matrix problems.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: chapter 11 (hash tables, for the map version) and chapter 14 (augmenting data structures, for range queries under updates).
• Sedgewick and Wayne, Algorithms: section 5.1, where key-indexed counting turns counts into cumulative positions with the same running-total idea.
• Steven Skiena, The Algorithm Design Manual: the sections on hashing and on data structures for range queries.
• Blelloch, "Prefix sums and their applications" (1990), the paper that treats prefix sums as a primitive of parallel algorithms.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.