23 questions using this pattern
Precompute cumulative sums to answer range sum queries in O(1) time. This transforms repeated O(n) range calculations into O(n) preprocessing plus O(1) per query, making it essential for problems involving subarray sums.
Imagine tracking your total running distance over a year. Instead of adding up daily distances each time someone asks "how far did you run from day 50 to day 75?", you keep a running total. The cumulative distance on day 75 minus day 49 instantly gives you the answer.
Another analogy: a bank account balance. To find how much you spent between two dates, you subtract the earlier balance from the later balance—no need to sum individual transactions.
A prefix sum array stores cumulative sums where prefix[i] = sum of all
elements from index 0 to i-1. This enables O(1) range sum queries:
sum(i, j) = prefix[j+1] - prefix[i]
The key insight is that any range sum can be computed from two prefix sums. Instead of iterating through the range (O(n) per query), we do O(n) preprocessing once and answer unlimited queries in O(1) each.
This pattern extends to:
def build_prefix(nums: list[int]) -> list[int]: prefix = [0] for num in nums: prefix.append(prefix[-1] + num) return prefix def range_sum(prefix: list[int], i: int, j: int) -> int: return prefix[j + 1] - prefix[i]We have an array [3, 1, 4, 1, 5, 9] and need to efficiently answer range sum queries like "sum from index 1 to 4".
Building prefix sum array:
Array: [3, 1, 4, 1, 5, 9]
Index: 0 1 2 3 4 5
prefix[0] = 0 (empty prefix)
prefix[1] = 0 + 3 = 3 (sum of first 1 element)
prefix[2] = 3 + 1 = 4 (sum of first 2 elements)
prefix[3] = 4 + 4 = 8
prefix[4] = 8 + 1 = 9
prefix[5] = 9 + 5 = 14
prefix[6] = 14 + 9 = 23
Prefix: [0, 3, 4, 8, 9, 14, 23]
Index: 0 1 2 3 4 5 6
Range sum query: sum(2, 4) = elements at indices 2, 3, 4
sum(2, 4) = prefix[5] - prefix[2]
= 14 - 4
= 10
Verification: arr[2] + arr[3] + arr[4] = 4 + 1 + 5 = 10 ✓
Subarray sum equals K using hash map:
Array: [1, 2, 3, -2, 5] K = 4
As we iterate, track prefix sums and look for prefix_sum - K:
i=0: prefix=1, need 1-4=-3, not found
i=1: prefix=3, need 3-4=-1, not found
i=2: prefix=6, need 6-4=2, not found
i=3: prefix=4, need 4-4=0, found! (empty prefix)
→ subarray [0:4] sums to 4
i=4: prefix=9, need 9-4=5, not found
Wait, also: prefix at i=1 is 3, at i=4 is 9-4=5... let me recalculate
Actually arr[1:3] = 2+3-2=3, arr[2:4]=3-2+5=6... checking for K=4:
subarray [0:4] → 1+2+3-2=4 ✓
Use this skeleton as a starting point for problems using this pattern:
def build_prefix_sum(arr: list[int]) -> list[int]:
"""Build prefix sum array. prefix[i] = sum of arr[0:i]."""
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]
return prefix
def range_sum(prefix: list[int], i: int, j: int) -> int:
"""Sum of elements from index i to j (inclusive)."""
return prefix[j + 1] - prefix[i]
def subarray_sum_equals_k(nums: list[int], k: int) -> int:
"""Count subarrays with sum equal to k."""
count = 0
prefix_sum = 0
# Map: prefix_sum -> count of occurrences
sum_count = {0: 1} # Empty prefix has sum 0
for num in nums:
prefix_sum += num
# If (prefix_sum - k) exists, those prefixes form valid subarrays
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
# Record current prefix sum
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return count
def product_except_self(nums: list[int]) -> list[int]:
"""Product of array except self without division."""
n = len(nums)
result = [1] * n
# Prefix products (left to right)
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Suffix products (right to left)
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
def matrix_region_sum(matrix: list[list[int]],
row1: int, col1: int,
row2: int, col2: int) -> int:
"""2D prefix sum for matrix region queries."""
# Build 2D prefix sum
m, n = len(matrix), len(matrix[0])
prefix = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
prefix[i][j] = (matrix[i-1][j-1]
+ prefix[i-1][j]
+ prefix[i][j-1]
- prefix[i-1][j-1])
# Query region sum using inclusion-exclusion
return (prefix[row2+1][col2+1]
- prefix[row1][col2+1]
- prefix[row2+1][col1]
+ prefix[row1][col1])Look for these keywords and patterns in problem descriptions:
Confusion about whether prefix[i] includes arr[i] or not leads to incorrect range sums.
Fix:
Convention: prefix[i] = sum of first i elements = arr[0:i].
So prefix[0] = 0 (empty), and range sum is prefix[j+1] - prefix[i].
Not initializing the hash map with {0: 1} misses subarrays starting
from index 0.
Fix:
Always initialize: sum_count = {0: 1}. This handles the case where the
subarray from the beginning has sum K.
Precompute cumulative sums for O(1) range queries. Foundation for other variations.
Examples: Range Sum Query - Immutable, Running Sum of 1d Array
Track prefix sums in a hash map to find subarrays summing to a target.
Key insight: prefix[j] - prefix[i] = target means subarray [i,j] works.
Examples: Subarray Sum Equals K, Contiguous Array
Same idea but with multiplication. Watch for zeros and consider using left/right products separately.
Examples: Product of Array Except Self
Extend to matrices for O(1) region sum queries. Uses inclusion-exclusion principle.
Examples: Range Sum Query 2D, Matrix Block Sum
Inverse of prefix sum. Store differences to support O(1) range updates. Prefix sum of difference array gives original.
Examples: Range Addition, Corporate Flight Bookings
Start here to build foundational understanding.
Master the pattern with these representative problems.
Test your mastery with complex variations.
Explore similar techniques:
Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.
Maintain a window of elements that slides through the data, tracking a constraint or computing aggregates. This transforms O(n*k) brute force into O(n) by incrementally updating the window instead of recalculating from scratch.
Prefix sums can grow very large when array elements are big, causing overflow in some languages.
Fix:
In Python this isn't an issue. In Java/C++, use long for prefix sums
or check constraints carefully.
Prefix sum works with negative numbers, but some may expect only positive sums and use wrong optimization (like sliding window).
Fix:
Prefix sum handles negatives correctly. But problems like "minimum sum subarray of size k" need different approaches when negatives are present.