Prefix Sums and Difference Arrays

Spend O(n) once to build cumulative info, then answer each range query in O(1). Same trick powers subarray counting, submatrix sums, and bulk range updates.

Prefix sum array

• Make it one longer than the list with a leading 0: prefix[i] = sum of the first i elements (indexes 0..i-1).
• Build: prefix[0] = 0, prefix[i+1] = prefix[i] + nums[i].
• Range sum of [l, r] inclusive = prefix[r+1] - prefix[l] in O(1). The leading 0 removes the l == 0 special case.
• nums=[3,1,4,1,5,9] -> prefix=[0,3,4,8,9,14,23]; range_sum(1,3) = prefix[4] - prefix[1] = 6.

Subarray sum equals k (prefix + hash map)

• Subarray i..j sums to k iff prefix[i] = running - k. Count earlier prefixes equal to running - k.
• Seed the map with {0: 1} (the empty prefix) so subarrays starting at index 0 are counted.
• One O(n) pass, O(n) space; handles negatives and overlaps (a sliding window cannot).

def subarray_sum_count(nums: list[int], k: int) -> int:
    counts, running, total = {0: 1}, 0, 0
    for x in nums:
        running += x
        total += counts.get(running - k, 0)
        counts[running] = counts.get(running, 0) + 1
    return total   # [1,2,3], k=3 -> 2 ; [1,1,1], k=2 -> 2

2-D prefix sum (submatrix)

• Padded table: P[i+1][j+1] = grid[i][j] + P[i][j+1] + P[i+1][j] - P[i][j] (inclusion-exclusion).
• Query (r1,c1)..(r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1].
• Build O(rows·cols), each query O(1).

Difference array (bulk range-add)

• Add val over [l, r]: diff[l] += val, diff[r+1] -= val (each O(1)). Realize with one prefix pass: running += diff[i]. Size diff as n+1 so r+1 is valid.
• Go-to for “+1 over every interval” (overlap counts): +1 at each start, -1 past each end.
• n=5, [(1,3,2),(2,4,3),(0,2,-1)] -> [-1, 1, 4, 5, 3].

Kadane’s max subarray (related running-value idea)

• Largest contiguous sum in O(n) time, O(1) space: current = max(x, current + x), track best.
• Init both to nums[0], not 0, or an all-negative list wrongly returns 0.

Pitfalls

• Range formula is prefix[r+1] - prefix[l]; prefix[l-1] breaks at l=0 (Python -1 wraps).
• Prefix array length n+1 with leading 0; diff array length n+1 for the r+1 write.
• Seed subarray-sum map with {0: 1}, not {}.

Summary table