The prefix sum idea
Naive subarray sum query: iterate from l to r, sum each element — O(n) per query. With n queries this is O(n²). The prefix sum builds a cumulative array in O(n), then any range sum query is O(1): ``` arr = [3, 1, 4, 1, 5, 9, 2, 6] prefix = [3, 4, 8, 9, 14, 23, 25, 31] sum(arr[2..5]) = prefix[5] - prefix[1] = 23 - 4 = 19 ``` Verify: 4 + 1 + 5 + 9 = 19. ✓
Template — basic prefix sum
```python # Build prefix sum (1-indexed for cleaner boundary handling) def build_prefix(arr): n = len(arr) prefix = [0] * (n + 1) # prefix[0] = 0 sentinel for i in range(n): prefix[i + 1] = prefix[i] + arr[i] return prefix def range_sum(prefix, l, r): # inclusive, 0-indexed return prefix[r + 1] - prefix[l] ``` The 1-indexed sentinel `prefix[0] = 0` avoids the l-1 edge case when l = 0. `range_sum(prefix, 0, 3)` = `prefix[4] - prefix[0]` — no boundary issues.
Template — Subarray Sum Equals K (LC 560)
Count subarrays that sum to exactly k. The key insight: `sum(i..j) = k` iff `prefix[j] - prefix[i-1] = k` iff `prefix[i-1] = prefix[j] - k`. So while building prefix sums, check if `(current_prefix - k)` was seen before. ```python def subarraySum(nums, k): from collections import defaultdict count = defaultdict(int) count[0] = 1 # empty prefix prefix = 0 result = 0 for num in nums: prefix += num result += count[prefix - k] # how many times (prefix - k) appeared count[prefix] += 1 return result ``` Time: O(n). Space: O(n). This same template solves LC 525 (Contiguous Array — replace values: 0→-1, look for prefix sum = 0).
Template — 2D prefix sum
For 2D range queries (sum of a rectangle in a matrix): ```python class NumMatrix: def __init__(self, matrix): m, n = len(matrix), len(matrix[0]) self.prefix = [[0] * (n + 1) for _ in range(m + 1)] for r in range(m): for c in range(n): self.prefix[r+1][c+1] = (matrix[r][c] + self.prefix[r][c+1] # top + self.prefix[r+1][c] # left - self.prefix[r][c]) # subtract top-left (counted twice) def sumRegion(self, r1, c1, r2, c2): # Inclusion-exclusion: full - top strip - left strip + top-left corner return (self.prefix[r2+1][c2+1] - self.prefix[r1][c2+1] - self.prefix[r2+1][c1] + self.prefix[r1][c1]) ``` LC 304 (Range Sum Query 2D). Build: O(m×n). Query: O(1).
Prefix sum + binary search
For problems asking for the smallest subarray with sum ≥ target, combine prefix sum with binary search: ```python def minSubArrayLen(target, nums): import bisect prefix = [0] for n in nums: prefix.append(prefix[-1] + n) result = float('inf') for i, p in enumerate(prefix): need = p + target j = bisect.bisect_left(prefix, need) if j < len(prefix): result = min(result, j - i) return result if result != float('inf') else 0 ``` Time: O(n log n). This is an alternative to the O(n) sliding window approach for LC 209 — useful to know both.