Prefix Sums

Use prefix sums when many queries aggregate overlapping ranges of an unchanged array, or when a subarray condition can become a relationship between two running totals.

1. Recipe: Answer Range Sums with Two Prefixes

Define prefix[i] = sum(nums[:i]). The extra leading zero represents an empty prefix and removes the special case at the left edge.

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

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

Here every query uses half-open [left, right), with 0 <= left <= right <= n. The prefix before left appears in both totals and cancels. For [3, -2, 5], the prefix array is [0, 3, 1, 6]; the sum of indices [1, 3) is 6 - 3 = 3. For inclusive [left, right], use prefix[right+1] - prefix[left], as in Range Sum Query.

Preprocessing takes $O(n)$ time and space; q queries take $O(q)$ total. Negative inputs are fine. An input update invalidates later prefixes, so updating the table can cost $O(n)$. Use a wide enough integer type for accumulated sums and counts.

2. Count or Locate Subarrays with a Target Sum

For a subarray ending at the current position, current_prefix - earlier_prefix = k. Thus look for earlier prefixes equal to current_prefix - k.

def count_sum_k(nums, k):
    frequency = {0: 1}
    total = answer = 0
    for value in nums:
        total += value
        answer += frequency.get(total - k, 0)
        frequency[total] = frequency.get(total, 0) + 1
    return answer

frequency counts only prefixes before the current endpoint. Seed {0: 1} to count ranges starting at index zero; query before inserting the current prefix so k = 0 does not count an empty subarray. For [0, 0] and k=0, the two iterations add 1 and 2, giving three nonempty subarrays.

With prefix positions 0..n, seed earliest/latest maps with {0: 0}; at position r, a matching earlier position l gives length r-l. These scans use expected $O(n)$ time and $O(n)$ space. Unlike sum-based sliding windows, they also work when values are negative.

Related transforms: for sums divisible by positive m, match equal prefix remainders; normalize negative remainders when the language requires it. For equal numbers of zeroes and ones, map 0 -> -1, 1 -> +1 and look for sum zero.

3. Prefix/Suffix Information and 2D Queries

Choose an aggregate that fits the question. A prefix count of predicate(value) answers “how many matching items are in this range?” Prefix XOR cancels using XOR. Prefix minimum and maximum cannot be subtracted to recover arbitrary range extrema.

For Find Pivot Index, keep left_sum and the total: the right side is total - left_sum - nums[i]. Compare before adding nums[i] to left_sum. For product-except-self, store each index's prefix product in the output, then multiply by a running suffix product; this avoids division and handles zeroes in $O(n)$ time with $O(1)$ auxiliary space excluding output.

For an R x C grid, let P[r][c] be the sum of rows < r and columns < c, with a zero row and column. Build:

P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]

The rectangle [r1,r2) x [c1,c2) sums to P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1]. Add the overlap back because it was subtracted twice. Build in $O(RC)$ time and space, query in $O(1)$; see Grids & Matrices.

4. Batch Range Additions with a Difference Array

When many updates add a value to a range and only the final array is needed, record where each contribution starts and stops.

def apply_additions(nums, updates):
    diff = [0] * (len(nums) + 1)
    for left, right, value in updates:
        diff[left] += value
        diff[right] -= value
    result = []
    running = 0
    for i, value in enumerate(nums):
        running += diff[i]
        result.append(value + running)
    return result

Updates use [left, right). The running sum carries an addition through the range and cancels it exactly at right. For an inclusive right endpoint, cancel at right+1. With q updates, this takes $O(n+q)$ time and $O(n)$ space. If queries and updates must be interleaved, consider a Fenwick or segment tree rather than rebuilding prefix sums after every update.

5. Key Takeaways

• Write the interval convention first. A leading zero makes [left,right) equal to prefix[right]-prefix[left].
• Count sum-k ranges by querying total-k before recording total; initialize the empty prefix.
• Longest ranges need the earliest matching prefix, whereas counting needs all matching starts.
• Use prefix sums for repeated static queries and difference arrays for batched additions. Neither makes arbitrary interleaved updates and queries constant-time.

Combine this topic with Sets & Maps for prefix lookups. Compare Sliding Windows when a contiguous range has a monotonic validity condition.