Prefix sum is one of the most elegant patterns in algorithmic problem solving. It transforms O(n) range queries into O(1) lookups. It enables O(n) solutions to subarray problems that would otherwise be O(n²). And once you master it, you'll recognize it instantly in dozens of LeetCode problems.
But here's the challenge: prefix sum isn't just about cumulative sums—it's a family of techniques that extends to 2D matrices, hash map combinations, difference arrays, and even XOR and product operations. Understanding when and how to apply each variant is what separates those who memorize solutions from those who truly master the pattern.
This comprehensive guide will teach you everything about prefix sum: all variants, when to use each pattern, the intuition behind why they work, common mistakes to avoid, and a systematic decision framework that works every time.
Prefix sum is a preprocessing technique where you precompute cumulative sums of an array, allowing you to answer range sum queries in constant time.
The fundamental idea: Instead of calculating the sum of elements from index i to j every time (which takes O(n)), we precompute cumulative sums once (O(n)) and then answer any query in O(1).
Example:
Original array: [3, 1, 4, 1, 5, 9, 2]
Prefix sum: [0, 3, 4, 8, 9, 14, 23, 25]
↑
We add a 0 at the beginning
Query: sum(2, 5) = sum of elements from index 2 to 5
Answer: prefix[6] - prefix[2] = 23 - 4 = 19
Verify: 4 + 1 + 5 + 9 = 19 ✓The power of prefix sum comes from a simple mathematical insight:
sum(i, j) = sum(0, j) - sum(0, i-1)
If we know the cumulative sum from the start to position j and the cumulative sum from the start to position i-1, we can get the sum of the range [i, j] by subtraction.
Visual proof:
Array: [3, 1, 4, 1, 5, 9, 2]
[0 1 2 3 4 5 6] ← indices
sum(0, 5) = 3 + 1 + 4 + 1 + 5 + 9 = 23
sum(0, 1) = 3 + 1 = 4
sum(2, 5) = sum(0, 5) - sum(0, 1)
= 23 - 4
= 19
= 4 + 1 + 5 + 9 ✓This is why prefix sum works: subtraction eliminates the unwanted prefix, leaving only the range we care about.
Let's see the transformation from naive to optimal:
Naive approach (O(n) per query):
def range_sum(arr, left, right):
total = 0
for i in range(left, right + 1):
total += arr[i]
return total
# For q queries: O(q × n)Prefix sum approach (O(1) per query after O(n) preprocessing):
# Preprocessing: O(n)
prefix = [0]
for num in arr:
prefix.append(prefix[-1] + num)
# Query: O(1)
def range_sum(left, right):
return prefix[right + 1] - prefix[left]
# For q queries: O(n + q)The tradeoff: We spend O(n) time and O(n) space upfront to make every subsequent query O(1). This is worth it when you have multiple queries or when you need to find subarrays efficiently.
Problem: Answer 1000 range sum queries on an array of size 10,000.
Brute force:
Prefix sum:
Result: Prefix sum is ~900× faster at the cost of linear space.
Prefix sum isn't one pattern—it's three distinct techniques that solve different types of problems. Understanding which variant to use is the key to mastering prefix sum.
The Pattern: Precompute cumulative sums to answer range sum queries in O(1).
When to use:
i to jWhy it works:
The cumulative sum property allows us to isolate any range by subtraction: sum(i, j) = prefix[j+1] - prefix[i].
Visual representation:
Array: [3, 1, 4, 1, 5]
Index: 0 1 2 3 4
Prefix: [0, 3, 4, 8, 9, 14]
Index: 0 1 2 3 4 5
sum(1, 3) = prefix[4] - prefix[1] = 9 - 3 = 6
Verify: 1 + 4 + 1 = 6 ✓Real-world analogy: Imagine a water tank with markings at different heights. To know how much water is between the 2-meter and 5-meter marks, you don't need to measure that section—you just subtract the total at 2 meters from the total at 5 meters.
Example problems: Range Sum Query (#303), Find Pivot Index (#724), Subarray Sum Equals K (#560)
The Pattern: Use prefix sum with a hash map to find subarrays that meet a target sum condition in O(n).
When to use:
Why it works:
If prefix[j] - prefix[i] = target, then the subarray from i+1 to j has sum equal to target. We can rearrange this to prefix[i] = prefix[j] - target. As we iterate, we check if prefix[j] - target exists in our hash map.
Visual representation:
Array: [1, 2, 3, 4], target = 6
prefix_sum = 0, map = {0: 1}
i=0: num=1, prefix=1, check 1-6=-5 (not in map), map={0:1, 1:1}
i=1: num=2, prefix=3, check 3-6=-3 (not in map), map={0:1, 1:1, 3:1}
i=2: num=3, prefix=6, check 6-6=0 (in map!), count=1, map={0:1, 1:1, 3:1, 6:1}
i=3: num=4, prefix=10, check 10-6=4 (not in map), map={0:1, 1:1, 3:1, 6:1, 10:1}
Found 1 subarray: [1,2,3] with sum 6Real-world analogy: You're tracking your bank balance. To find periods where you spent exactly $100, you look for two dates where the balance difference is $100. The hash map stores all previous balances for quick lookup.
Example problems: Subarray Sum Equals K (#560), Continuous Subarray Sum (#523), Subarray Sum Divisible by K (#974)
The Pattern: Extend prefix sum to 2D matrices using the inclusion-exclusion principle to answer rectangle sum queries in O(1).
When to use:
Why it works:
We use the inclusion-exclusion principle: to get the sum of a rectangle, we add the large rectangle, subtract the two overlapping regions, and add back the doubly-subtracted corner.
Visual representation:
Matrix:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
Prefix sum matrix (with padding):
[0, 0, 0, 0]
[0, 1, 3, 6]
[0, 5, 12, 21]
[0, 12, 27, 45]
Query: sum of rectangle (1,1) to (2,2) (values 5,6,8,9)
= prefix[3][3] - prefix[0][3] - prefix[3][0] + prefix[0][0]
= 45 - 6 - 12 + 0 = 27
Verify: 5 + 6 + 8 + 9 = 28... wait, let me recalculate
Actually for (1,1) to (2,2) in 0-indexed:
= prefix[2+1][2+1] - prefix[1-1+1][2+1] - prefix[2+1][1-1+1] + prefix[1-1+1][1-1+1]
= prefix[3][3] - prefix[1][3] - prefix[3][1] + prefix[1][1]
= 45 - 6 - 12 + 1 = 28 ✓Real-world analogy: Imagine a rainfall map where each cell shows cumulative rainfall from the top-left corner to that position. To find rainfall in a specific region, you use the four corners to calculate the exact area.
Example problems: Range Sum Query 2D (#304), Matrix Block Sum (#1314)
Choosing the right pattern is crucial. Here's a systematic decision framework:
Question 1: What's the data structure?
├─ 1D Array → Continue to Question 2
├─ 2D Matrix → Consider 2D Prefix Sum
└─ Other → Prefix sum likely not applicable
Question 2: What's the goal?
├─ Range sum queries (multiple) → Basic Prefix Sum ✓
├─ Find subarrays with target sum → Prefix Sum + Hash Map ✓
├─ Range updates (multiple) → Difference Array ✓
├─ Maximum/minimum subarray → Kadane's Algorithm (not prefix sum)
└─ Variable-size window with condition → Sliding Window (not prefix sum)
Question 3: Is the array static or dynamic?
├─ Static (no updates) → Prefix Sum ✓
├─ Few updates, many queries → Rebuild prefix sum
└─ Many updates → Segment Tree / Fenwick Tree
Question 4: Space constraints?
├─ O(n) space allowed → Prefix Sum ✓
└─ Must be O(1) → Can't use prefix sumUse Basic Prefix Sum when you see:
Use Prefix Sum + Hash Map when you see:
Use 2D Prefix Sum when you see:
Don't use Prefix Sum when you see:
class RangeSumQuery:
"""
For: Multiple range sum queries on static array
Time: O(n) preprocessing, O(1) per query
Space: O(n)
"""
def __init__(self, nums):
# Build prefix sum array with padding
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
def sumRange(self, left, right):
# Query in O(1)
return self.prefix[right + 1] - self.prefix[left]JavaScript:
class RangeSumQuery {
constructor(nums) {
this.prefix = [0];
for (const num of nums) {
this.prefix.push(this.prefix[this.prefix.length - 1] + num);
}
}
sumRange(left, right) {
return this.prefix[right + 1] - this.prefix[left];
}
}Java:
class RangeSumQuery {
private int[] prefix;
public RangeSumQuery(int[] nums) {
prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
public int sumRange(int left, int right) {
return prefix[right + 1] - prefix[left];
}
}def subarray_sum_equals_k(nums, k):
"""
For: Finding/counting subarrays with target sum
Time: O(n)
Space: O(n)
"""
count = 0
prefix_sum = 0
# Key: prefix sum, Value: frequency
# Initialize with {0: 1} to handle subarrays starting from index 0
sum_count = {0: 1}
for num in nums:
prefix_sum += num
# Check if (prefix_sum - k) exists
# If yes, we found subarray(s) with sum k
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
# Add current prefix sum to map
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return countJavaScript:
function subarraySumEqualsK(nums, k) {
let count = 0;
let prefixSum = 0;
const sumCount = new Map([[0, 1]]);
for (const num of nums) {
prefixSum += num;
if (sumCount.has(prefixSum - k)) {
count += sumCount.get(prefixSum - k);
}
sumCount.set(prefixSum, (sumCount.get(prefixSum) || 0) + 1);
}
return count;
}Java:
public int subarraySumEqualsK(int[] nums, int k) {
int count = 0;
int prefixSum = 0;
Map<Integer, Integer> sumCount = new HashMap<>();
sumCount.put(0, 1);
for (int num : nums) {
prefixSum += num;
if (sumCount.containsKey(prefixSum - k)) {
count += sumCount.get(prefixSum - k);
}
sumCount.put(prefixSum, sumCount.getOrDefault(prefixSum, 0) + 1);
}
return count;
}class RangeSumQuery2D:
"""
For: Multiple rectangle sum queries on static matrix
Time: O(rows × cols) preprocessing, O(1) per query
Space: O(rows × cols)
"""
def __init__(self, matrix):
if not matrix or not matrix[0]:
self.prefix = [[]]
return
rows, cols = len(matrix), len(matrix[0])
# Pad with extra row and column of zeros
self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
# Build 2D prefix sum using inclusion-exclusion
for r in range(1, rows + 1):
for c in range(1, cols + 1):
self.prefix[r][c] = (
matrix[r-1][c-1] +
self.prefix[r-1][c] +
self.prefix[r][c-1] -
self.prefix[r-1][c-1]
)
def sumRegion(self, row1, col1, row2, col2):
# Query rectangle sum in O(1)
return (
self.prefix[row2+1][col2+1] -
self.prefix[row1][col2+1] -
self.prefix[row2+1][col1] +
self.prefix[row1][col1]
)JavaScript:
class RangeSumQuery2D {
constructor(matrix) {
if (!matrix || !matrix.length || !matrix[0].length) {
this.prefix = [[]];
return;
}
const rows = matrix.length, cols = matrix[0].length;
this.prefix = Array(rows + 1).fill(0)
.map(() => Array(cols + 1).fill(0));
for (let r = 1; r <= rows; r++) {
for (let c = 1; c <= cols; c++) {
this.prefix[r][c] =
matrix[r-1][c-1] +
this.prefix[r-1][c] +
this.prefix[r][c-1] -
this.prefix[r-1][c-1];
}
}
}
sumRegion(row1, col1, row2, col2) {
return (
this.prefix[row2+1][col2+1] -
this.prefix[row1][col2+1] -
this.prefix[row2+1][col1] +
this.prefix[row1][col1]
);
}
}Java:
class RangeSumQuery2D {
private int[][] prefix;
public RangeSumQuery2D(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
prefix = new int[0][0];
return;
}
int rows = matrix.length, cols = matrix[0].length;
prefix = new int[rows + 1][cols + 1];
for (int r = 1; r <= rows; r++) {
for (int c = 1; c <= cols; c++) {
prefix[r][c] =
matrix[r-1][c-1] +
prefix[r-1][c] +
prefix[r][c-1] -
prefix[r-1][c-1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return
prefix[row2+1][col2+1] -
prefix[row1][col2+1] -
prefix[row2+1][col1] +
prefix[row1][col1];
}
}1. Range Sum Query - Immutable (LeetCode #303)
class NumArray:
def __init__(self, nums):
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
def sumRange(self, left, right):
return self.prefix[right + 1] - self.prefix[left]
# Usage
obj = NumArray([1, 2, 3, 4, 5])
print(obj.sumRange(1, 3)) # 2 + 3 + 4 = 9
print(obj.sumRange(0, 4)) # 1 + 2 + 3 + 4 + 5 = 15Why it works: We precompute cumulative sums once, then answer each query in O(1) by subtraction.
2. Find Pivot Index (LeetCode #724)
def pivotIndex(nums):
"""
Find index where left sum equals right sum
"""
total = sum(nums)
left_sum = 0
for i, num in enumerate(nums):
# Right sum = total - left_sum - current element
right_sum = total - left_sum - num
if left_sum == right_sum:
return i
left_sum += num
return -1
# Example
print(pivotIndex([1, 7, 3, 6, 5, 6])) # 3
# Left: 1+7+3 = 11, Right: 5+6 = 11Why it works: We maintain a running sum (prefix sum) and calculate the right sum using total - left_sum - current.
See detailed guide: 1D Prefix Sum Template
1. Subarray Sum Equals K (LeetCode #560)
def subarraySum(nums, k):
"""
Count subarrays with sum equal to k
Time: O(n), Space: O(n)
"""
count = 0
prefix_sum = 0
sum_count = {0: 1} # Critical: handle subarrays from index 0
for num in nums:
prefix_sum += num
# If (prefix_sum - k) exists, we found subarray(s)
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return count
# Example
print(subarraySum([1, 2, 3, 4], 6)) # 1 (subarray [2,3,1] doesn't exist, but [2,4] doesn't either... actually [2,3,1] is not contiguous)
# Actually: [1,2,3] = 6, so answer is 1Why it works: If prefix[j] - prefix[i] = k, then subarray from i+1 to j has sum k. We rearrange to prefix[i] = prefix[j] - k and check if it exists in our map.
2. Continuous Subarray Sum (LeetCode #523)
def checkSubarraySum(nums, k):
"""
Check if array has subarray (size >= 2) with sum divisible by k
Time: O(n), Space: O(k)
"""
# Key: remainder, Value: earliest index
remainder_index = {0: -1} # Handle subarray from start
prefix_sum = 0
for i, num in enumerate(nums):
prefix_sum += num
remainder = prefix_sum % k
if remainder in remainder_index:
# Check if subarray length >= 2
if i - remainder_index[remainder] >= 2:
return True
else:
remainder_index[remainder] = i
return False
# Example
print(checkSubarraySum([23, 2, 4, 6, 7], 6)) # True
# [2,4] has sum 6, divisible by 6Why it works: If two prefix sums have the same remainder when divided by k, the subarray between them is divisible by k.
See detailed guide: Prefix Sum + Hash Map Technique
1. Range Sum Query 2D - Immutable (LeetCode #304)
class NumMatrix:
def __init__(self, matrix):
if not matrix or not matrix[0]:
self.prefix = [[]]
return
rows, cols = len(matrix), len(matrix[0])
self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(1, rows + 1):
for c in range(1, cols + 1):
self.prefix[r][c] = (
matrix[r-1][c-1] +
self.prefix[r-1][c] +
self.prefix[r][c-1] -
self.prefix[r-1][c-1]
)
def sumRegion(self, row1, col1, row2, col2):
return (
self.prefix[row2+1][col2+1] -
self.prefix[row1][col2+1] -
self.prefix[row2+1][col1] +
self.prefix[row1][col1]
)
# Usage
matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
obj = NumMatrix(matrix)
print(obj.sumRegion(2, 1, 4, 3)) # Sum of rectangleWhy it works: We use inclusion-exclusion principle to calculate rectangle sums in O(1).
See detailed guide: 2D Prefix Sum Matrix
The inverse of prefix sum: enables O(1) range updates.
def range_addition(length, updates):
"""
LeetCode #370: Range Addition
Apply multiple range updates efficiently
Time: O(n + k) where k = number of updates
"""
diff = [0] * (length + 1)
# Apply all updates to difference array: O(k)
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Reconstruct final array with prefix sum: O(n)
result = []
current = 0
for i in range(length):
current += diff[i]
result.append(current)
return result
# Example
updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]
print(range_addition(5, updates))
# [-2, 0, 3, 5, 3]Why it works: Difference array records changes. Adding to diff[start] and subtracting from diff[end+1] creates a "plateau" when we apply prefix sum.
See detailed guide: Difference Array
Apply prefix sum logic to XOR operations.
def xor_queries(arr, queries):
"""
LeetCode #1310: XOR Queries of a Subarray
"""
prefix_xor = [0]
for num in arr:
prefix_xor.append(prefix_xor[-1] ^ num)
result = []
for left, right in queries:
# XOR property: a ^ a = 0
result.append(prefix_xor[right + 1] ^ prefix_xor[left])
return resultWhy it works: XOR has the property a ^ a = 0, so prefix[j] ^ prefix[i] = arr[i+1] ^ ... ^ arr[j].
Apply prefix sum logic to multiplication.
def productExceptSelf(nums):
"""
LeetCode #238: Product of Array Except Self
Without division, O(1) extra space
"""
n = len(nums)
result = [1] * n
# Build prefix products (left to right)
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Build suffix products (right to left) and multiply
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
# Example
print(productExceptSelf([1, 2, 3, 4]))
# [24, 12, 8, 6]Why it works: For each position, we multiply the product of all elements to its left by the product of all elements to its right.
See detailed guide: Prefix XOR and Product Variants
❌ Wrong:
# Forgetting to add 1 to right index
sum_range = prefix[right] - prefix[left]✅ Correct:
# Correct formula
sum_range = prefix[right + 1] - prefix[left]See guide: Off-by-One Errors
❌ Wrong:
prefix = []
for num in nums:
prefix.append(prefix[-1] + num if prefix else num)✅ Correct:
prefix = [0] # Critical: start with 0
for num in nums:
prefix.append(prefix[-1] + num)Why: The initial 0 allows us to calculate sums starting from index 0 without special cases.
❌ Wrong:
sum_count = {} # Missing base case✅ Correct:
sum_count = {0: 1} # Handle subarrays from index 0See guide: Hash Map Initialization
❌ Wrong pattern choice:
# Using prefix sum for "longest substring without repeating characters"
# This is a sliding window problem!✅ Correct:
See guide: Prefix Sum vs Sliding Window
Step 1: Identify the Problem Type
Step 2: Check Array Properties
Step 3: Analyze Query Pattern
Step 4: Space Constraints
See complete guide: Pattern Recognition
Preprocessing: O(n) for 1D, O(rows × cols) for 2D
Query: O(1)
Total for q queries: O(n + q)
1D Prefix Sum: O(n)
2D Prefix Sum: O(rows × cols)
Hash Map variant: O(n) for the map
Worth it when:
Not worth it when:
Break-even point: Usually when q ≥ 2, prefix sum is already faster.
See detailed analysis: Complexity Analysis
Master prefix sum with these problems:
Beginner (Basic Prefix Sum):
Intermediate (Prefix Sum + Hash Map):
4. Subarray Sum Equals K (#560)
5. Continuous Subarray Sum (#523)
6. Subarray Sums Divisible by K (#974)
7. Contiguous Array (#525)
Intermediate (2D Prefix Sum):
8. Range Sum Query 2D - Immutable (#304)
9. Matrix Block Sum (#1314)
Advanced (Variants):
10. Product of Array Except Self (#238)
11. XOR Queries of a Subarray (#1310)
12. Range Addition (#370)
13. Corporate Flight Bookings (#1109)
14. Car Pooling (#1094)
Expert (Complex Applications):
15. Maximum Size Subarray Sum Equals k (#325)
16. Minimum Size Subarray Sum (#209) - compare with sliding window
17. Count Number of Nice Subarrays (#1248)
Q: When should I use prefix sum vs sliding window?
A: Use prefix sum for:
Use sliding window for:
See Prefix Sum vs Sliding Window.
Q: Why do we initialize the hash map with {0: 1}?
A: To handle subarrays that start from index 0. Without it, we'd miss cases like [1, 2, 3] with target 6 (the entire array). See Hash Map Initialization.
Q: Can prefix sum handle array updates?
A: Not efficiently. Prefix sum is for static arrays. If you need frequent updates:
Q: What's the difference between prefix sum and difference array?
A: They're inverses:
See Difference Array.
Q: How do I avoid off-by-one errors?
A: Follow these rules:
prefix = [0]sum(i, j) = prefix[j+1] - prefix[i]See Off-by-One Errors.
Q: Does prefix sum work with negative numbers?
A: Yes! Prefix sum handles negatives perfectly. In fact, negative numbers make sliding window fail, so prefix sum + hash map becomes the only O(n) solution. See Negative Numbers.
Prefix sum is a fundamental pattern that transforms expensive range queries into constant-time lookups and enables linear-time solutions to subarray problems.
Key principles:
The three main templates:
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
sum_range = prefix[right+1] - prefix[left]sum_count = {0: 1}
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1prefix[r][c] = matrix[r-1][c-1] + prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1]
sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]When to use:
Master these templates, and you'll solve dozens of LeetCode problems with confidence. For specific techniques, see 1D Template, Hash Map Technique, and 2D Matrix.
Next time you see "range sum" or "subarray sum," reach for prefix sum.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free