➕ Prefix Sums
Precompute running totals once; any range sum is P[r + 1] - P[l].
Recognize the pattern
Many range-sum queries on an array that doesn't change → prefix array, O(1) per query
"Left sum vs right sum" at each index → total - left - current gives the right side
Count subarrays with sum = k (negatives allowed) → prefix sum + Counter of earlier prefixes
Longest subarray with sum k / equal 0s and 1s → prefix (or +1/-1 balance) + first-index map
Sum divisible by k / multiple of k → map prefix % k to its first index or count
Sum of a sub-rectangle, many times → 2D prefix sums with a padding row and column
Many "add v to range l..r" updates, read once → difference array + one prefix pass
1D prefix array
P[i] = sum of nums[:i]; len(P) == n + 1. Range l..r inclusive is P[r + 1] - P[l].
from itertools import accumulate
def build_prefix(nums: list[int]) -> list[int]:
return list(accumulate(nums, initial=0))
def range_sum(P: list[int], l: int, r: int) -> int:
return P[r + 1] - P[l]
Count subarrays with sum k
Seed with {0: 1} (the empty prefix). Look up before recording the current prefix.
from collections import Counter
def count_sum_k(nums: list[int], k: int) -> int:
seen = Counter({0: 1})
prefix = count = 0
for x in nums:
prefix += x
count += seen[prefix - k]
seen[prefix] += 1
return count
Longest subarray (first-index map)
Seed with {0: -1} and store each key only the first time. For equal 0s/1s add 1 if x else -1 and use k = 0. For multiples of k, key on prefix % k.
def longest_sum_k(nums: list[int], k: int) -> int:
first = {0: -1}
prefix = best = 0
for i, x in enumerate(nums):
prefix += x
if prefix - k in first:
best = max(best, i - first[prefix - k])
if prefix not in first:
first[prefix] = i
return best
2D prefix sums
def build_2d(grid: list[list[int]]) -> list[list[int]]:
R, C = len(grid), len(grid[0])
P = [[0] * (C + 1) for _ in range(R + 1)]
for r in range(R):
for c in range(C):
P[r + 1][c + 1] = (grid[r][c] + P[r][c + 1]
+ P[r + 1][c] - P[r][c])
return P
def rect(P, r1: int, c1: int, r2: int, c2: int) -> int:
return (P[r2 + 1][c2 + 1] - P[r1][c2 + 1]
- P[r2 + 1][c1] + P[r1][c1])
Difference array (range updates)
from itertools import accumulate
def range_add(n: int, updates) -> list[int]:
diff = [0] * (n + 1)
for l, r, v in updates:
diff[l] += v
diff[r + 1] -= v
return list(accumulate(diff[:n]))
Prefix + monotonic deque (sum ≥ k, negatives)
Keep candidate start indices with increasing prefix values. Pop from the front while the window is long enough; pop from the back any start that is no better than the current one.
from collections import deque
def shortest_at_least_k(nums: list[int], k: int) -> int:
P = [0]
for x in nums:
P.append(P[-1] + x)
best, dq = len(nums) + 1, deque()
for j, pj in enumerate(P):
while dq and pj - P[dq[0]] >= k:
best = min(best, j - dq.popleft())
while dq and P[dq[-1]] >= pj:
dq.pop()
dq.append(j)
return best if best <= len(nums) else -1
Operation costs
| Operation | Time | Space |
|---|---|---|
| Build 1D prefix array | O(n) | O(n) |
| Range sum query | O(1) | O(1) |
| Count / longest subarray with sum k | O(n) | O(n) |
| Build 2D prefix (R × C) | O(R·C) | O(R·C) |
| Rectangle sum query | O(1) | O(1) |
| Difference array: m updates + rebuild | O(m + n) | O(n) |
Watch for
Off-by-one: with a leading 0 the range l..r is P[r + 1] - P[l], not P[r] - P[l - 1].
Forgetting to seed the map ({0: 1} for counting, {0: -1} for lengths) misses subarrays that start at index 0.
Recording the current prefix before looking up prefix - k lets k = 0 count empty subarrays.
For the longest subarray, overwriting the stored index with a later one shortens the answer: keep the first.
Sliding window needs non-negative numbers; with negatives use prefix sum + hash map (or a monotonic deque for sum ≥ k).
Difference arrays need n + 1 slots so diff[r + 1] is safe when r = n - 1.