Introduction
Prefix sums enable O(1) range sum queries after O(n) preprocessing. The key constraint: the array cannot be updated. For mutable arrays, use segment trees.
Example:
nums = [3, 5, 2, 7, 1]
prefixSum = [3, 8, 10, 17, 18]Each prefixSum[i] = sum of nums[0..i]. We can define this recursively: PS[i] = PS[i-1] + nums[i], with PS[-1] = 0.
Range Sum Query: Sum of [l, r] = prefixSum[r] - prefixSum[l-1]
Example: sum([1,3]) = sum([5,2,7]) = PS[3] - PS[0] = 17 - 3 = 14
Pro tip: Initialize with a 0 at the end so PS[-1] = 0. This simplifies edge cases when l = 0.
Generalization: Any operation with an inverse can use this pattern:
- Addition (+) / Subtraction (-): Prefix Sum
- Multiplication (*) / Division (/): Prefix Product
- XOR (^) / XOR (^): Prefix XOR (XOR is its own inverse!)
Formula: result[l,r] = prefix[r] (inverse_op) prefix[l-1]
Initialize prefix[-1] to the identity element (0 for +, 1 for *, 0 for ^).
O(n) build, O(1) queryO(n)Prefix Sum Template
Build prefix sum array and query range sums in O(1).
# Building prefix sum
from itertools import accumulate
nums = [3, 5, 2, 7, 1]
prefix = list(accumulate(nums)) # [3, 8, 10, 17, 18]
prefix.append(0) # Add 0 at end for easier indexing: prefix[-1] = 0
# Range sum query [l, r] (inclusive)
def range_sum(l, r):
return prefix[r] - prefix[l-1]
# Examples:
# range_sum(0, 4) = prefix[4] - prefix[-1] = 18 - 0 = 18
# range_sum(1, 3) = prefix[3] - prefix[0] = 17 - 3 = 14Prefix Variants
Prefix product and prefix XOR follow the same pattern.
import operator
from itertools import accumulate
nums = [3, 5, 2, 7, 1]
# Prefix Product
prefix_prod = list(accumulate(nums, operator.mul)) # [3, 15, 30, 210, 210]
# Range product [l,r] = prefix_prod[r] // prefix_prod[l-1]
# Prefix XOR
prefix_xor = list(accumulate(nums, operator.xor)) # [3, 6, 4, 3, 2]
# Range XOR [l,r] = prefix_xor[r] ^ prefix_xor[l-1]
# Suffix sum (just reverse, compute, reverse back)
suffix = list(accumulate(nums[::-1]))[::-1] # [18, 15, 10, 8, 1]2D Prefix Sum
Extend prefix sums to 2D matrices for O(1) rectangular region sum queries.
Building 2D Prefix Sum:
PS[i][j] = grid[i][j] + PS[i-1][j] + PS[i][j-1] - PS[i-1][j-1]
Querying rectangle (r1,c1) to (r2,c2):
sum = PS[r2][c2] - PS[r2][c1-1] - PS[r1-1][c2] + PS[r1-1][c1-1]
Think of it as inclusion-exclusion: add the full rectangle, subtract the left and top portions, add back the double-subtracted corner.
2D Prefix Sum Template
Build and query 2D prefix sums.
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
# Pad with zeros for easier boundary handling
self.ps = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
self.ps[i][j] = (matrix[i-1][j-1] +
self.ps[i-1][j] +
self.ps[i][j-1] -
self.ps[i-1][j-1])
def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
# Adjust for 1-indexed prefix sum array
r1, c1, r2, c2 = r1 + 1, c1 + 1, r2 + 1, c2 + 1
return (self.ps[r2][c2] - self.ps[r2][c1-1] -
self.ps[r1-1][c2] + self.ps[r1-1][c1-1])Problems
Practice problems for prefix sums.
01Range Sum Query - ImmutableEasy
Given an array nums, handle multiple queries to calculate sum of elements between indices left and right inclusive.
class NumArray:
def __init__(self, nums: List[int]):
self.prefix = list(accumulate(nums))
self.prefix.append(0) # prefix[-1] = 0
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right] - self.prefix[left - 1]O(n) init, O(1) queryO(n)Direct application of prefix sum. The append(0) trick makes prefix[-1] = 0, handling the left = 0 case cleanly.
02Range Sum Query 2D - ImmutableMedium
Given a 2D matrix, handle multiple queries to calculate sum of elements inside a rectangle defined by (row1, col1) to (row2, col2).
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
self.ps = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
self.ps[i][j] = (matrix[i-1][j-1] + self.ps[i-1][j] +
self.ps[i][j-1] - self.ps[i-1][j-1])
def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
r1, c1, r2, c2 = r1+1, c1+1, r2+1, c2+1
return (self.ps[r2][c2] - self.ps[r2][c1-1] -
self.ps[r1-1][c2] + self.ps[r1-1][c1-1])O(mn) init, O(1) queryO(mn)2D prefix sum with inclusion-exclusion. Pad with zeros to avoid boundary checks. The formula subtracts left and top portions, then adds back the double-subtracted corner.
03Product of Array Except SelfMedium
Return an array where answer[i] is the product of all elements except nums[i]. Must be O(n) time without division.
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [1] * n
# First pass: prefix products (left of each index)
prefix = 1
for i in range(n):
res[i] = prefix
prefix *= nums[i]
# Second pass: multiply by suffix products (right of each index)
suffix = 1
for i in range(n - 1, -1, -1):
res[i] *= suffix
suffix *= nums[i]
return resO(n)O(1) extra (output not counted)Product except self = prefix_product[i-1] × suffix_product[i+1]. Two passes: first builds prefix products into result, second multiplies by suffix products. O(1) extra space by computing on the fly.
04Subarray Sum Equals KMedium
Given an array nums and integer k, return the total number of subarrays whose sum equals k.
def subarraySum(self, nums: List[int], k: int) -> int:
count = 0
prefix_sum = 0
seen = defaultdict(int)
seen[0] = 1 # Empty prefix has sum 0
for num in nums:
prefix_sum += num
# If prefix_sum - k exists, we found subarrays summing to k
count += seen[prefix_sum - k]
seen[prefix_sum] += 1
return countO(n)O(n)Key insight: if prefix[j] - prefix[i] = k, then subarray (i,j] sums to k. Use a hashmap to count prefix sums seen. For each position, check how many times (current_prefix - k) appeared before.
05Find The Original Array of Prefix XorMedium
Given prefix XOR array pref, find the original array arr where pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].
def findArray(self, pref: List[int]) -> List[int]:
# arr[i] = pref[i] ^ pref[i-1]
# Because: pref[i] ^ pref[i-1] = (arr[0]^...^arr[i]) ^ (arr[0]^...^arr[i-1])
# = arr[i] (all others cancel out)
for i in range(len(pref) - 1, 0, -1):
pref[i] = pref[i] ^ pref[i - 1]
return prefO(n)O(1)Reverse the prefix XOR operation. Since XOR is its own inverse: arr[i] = pref[i] ^ pref[i-1]. The key insight is that a ^ a = 0, so XORing consecutive prefix values cancels all elements except arr[i].
06Minimum Size Subarray SumMedium
Given array of positive integers and target, find minimal length subarray with sum >= target. Return 0 if none exists.
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# Two approaches: prefix sum + binary search, or sliding window
# Approach 1: Sliding window (better for positive numbers)
left = 0
curr_sum = 0
res = inf
for right in range(len(nums)):
curr_sum += nums[right]
while curr_sum >= target:
res = min(res, right - left + 1)
curr_sum -= nums[left]
left += 1
return res if res != inf else 0
# Approach 2: Prefix sum + binary search
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
prefix = list(accumulate(nums))
prefix.append(0)
res = inf
for r in range(len(nums)):
if prefix[r] >= target:
# Find smallest l where prefix[r] - prefix[l-1] >= target
# i.e., prefix[l-1] <= prefix[r] - target
l = bisect_right(prefix, prefix[r] - target)
res = min(res, r - l + 1)
return res if res != inf else 0O(n) sliding window, O(n log n) binary searchO(1) or O(n)For positive numbers, sliding window is optimal. Prefix sum + binary search works for any array but is slower. Binary search finds the rightmost valid left boundary.
07Minimum Time to Visit All HousesMedium
Houses arranged in circle with forward/backward roads. Find minimum time to visit houses in order given by queries.
def minTotalTime(self, forward: List[int], backward: List[int], queries: List[int]) -> int:
n = len(forward)
# Prefix sums for forward direction (0 -> 1 -> 2 -> ... -> n-1 -> 0)
fwd_prefix = [0] * (n + 1)
for i in range(n):
fwd_prefix[i + 1] = fwd_prefix[i] + forward[i]
total_fwd = fwd_prefix[n]
# Prefix sums for backward direction (0 -> n-1 -> n-2 -> ... -> 1 -> 0)
bwd_prefix = [0] * (n + 1)
for i in range(n):
bwd_prefix[i + 1] = bwd_prefix[i] + backward[(n - i) % n]
total_bwd = bwd_prefix[n]
def dist(src, dst):
if src == dst:
return 0
# Forward distance
fwd_dist = (fwd_prefix[dst] - fwd_prefix[src]) % total_fwd
if dst < src:
fwd_dist = total_fwd - fwd_prefix[src] + fwd_prefix[dst]
# Backward distance
bwd_dist = (bwd_prefix[n - dst] - bwd_prefix[n - src]) % total_bwd
if dst > src:
bwd_dist = total_bwd - bwd_prefix[n - src] + bwd_prefix[n - dst]
return min(fwd_dist, bwd_dist)
total = 0
curr = 0
for q in queries:
total += dist(curr, q)
curr = q
return totalO(n + q)O(n)Build prefix sums for both forward and backward circular paths. For each query, compute min of forward/backward distances using prefix sums.