🎯 Prefix Sum
1️⃣ Core Framework
When discussing Prefix Sum, I frame it as:
- What problem pattern it solves
- Why prefix sum improves range query performance
- One-dimensional prefix sum
- Prefix sum with hash map
- Subarray sum equals k
- Range sum query
- Difference array relationship
- Two-dimensional prefix sum
- Common edge cases
- Senior-level explanation
2️⃣ What Problem Are We Solving?
Prefix sum is used when we need to answer repeated range-sum or subarray-sum questions efficiently.
It is commonly used for:
- Range sum queries
- Subarray sum equals target
- Count subarrays with certain sum
- Find equilibrium index
- Product except self style reasoning
- Difference array problems
- 2D matrix region sum
- Optimization from repeated summation
The core idea is:
Precompute cumulative sums
so that any range sum can be calculated quickly.
👉 Interview Answer
Prefix sum is a preprocessing technique that stores cumulative sums.
It allows us to calculate the sum of any subarray in O(1) time after O(n) preprocessing.
It is especially useful when we need repeated range queries or when subarray sums can be transformed into differences between two prefix sums.
3️⃣ Why Prefix Sum Works
Brute Force Problem
Suppose we want the sum from index left to right.
A brute-force approach is:
total = 0
for i in range(left, right + 1):
total += nums[i]
This takes:
O(n) per query
If there are many queries, this becomes expensive.
Prefix Sum Optimization
Create an array where:
prefix[i] = sum of nums[0] to nums[i - 1]
Then:
sum(left, right) = prefix[right + 1] - prefix[left]
Example
nums = [2, 4, 6, 8]
prefix = [0, 2, 6, 12, 20]
Range sum from index 1 to 3:
nums[1] + nums[2] + nums[3]
= 4 + 6 + 8
= 18
Using prefix sum:
prefix[4] - prefix[1]
= 20 - 2
= 18
👉 Interview Answer
Prefix sum works because the sum of a range can be represented as the difference between two cumulative sums.
If prefix[i] stores the sum before index i, then the sum from left to right is prefix[right + 1] minus prefix[left].
This avoids recomputing the same sums repeatedly.
4️⃣ One-Dimensional Prefix Sum
Standard Build
def build_prefix(nums):
prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
Range Query
def range_sum(prefix, left, right):
return prefix[right + 1] - prefix[left]
Why Use Length n + 1?
Using an extra leading zero makes boundary handling easier.
prefix[0] = 0
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
Then all range sums use the same formula:
prefix[right + 1] - prefix[left]
👉 Interview Answer
I usually build prefix sum with length n + 1 and set prefix[0] to zero.
This makes the range-sum formula clean.
The sum from left to right inclusive is prefix[right + 1] - prefix[left].
It also avoids special cases when the range starts at index zero.
5️⃣ Range Sum Query
Problem
Given an array, answer multiple range sum queries.
nums = [1, 3, 5, 7, 9]
sumRange(1, 3) = 3 + 5 + 7 = 15
sumRange(0, 4) = 25
Code
class NumArray:
def __init__(self, nums):
self.prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
self.prefix[i + 1] = self.prefix[i] + nums[i]
def sumRange(self, left, right):
return self.prefix[right + 1] - self.prefix[left]
Complexity
Build: O(n)
Query: O(1)
Space: O(n)
👉 Interview Answer
For immutable range sum queries, I preprocess a prefix sum array in O(n).
Each query can then be answered in O(1) by subtracting two prefix sums.
This is a classic trade-off where we use extra memory to make repeated queries faster.
6️⃣ Prefix Sum and Subarray Sum
Key Formula
For a subarray from i to j:
sum(i, j) = prefix[j + 1] - prefix[i]
If we want:
sum(i, j) = k
Then:
prefix[j + 1] - prefix[i] = k
Rearrange:
prefix[i] = prefix[j + 1] - k
This means:
At current prefix sum,
look for whether current_sum - k appeared before.
👉 Interview Answer
Many subarray-sum problems can be transformed using prefix sums.
If current_sum is the prefix sum up to the current index, and we want a previous prefix such that current_sum - previous_prefix equals k, then previous_prefix must be current_sum - k.
This is why prefix sum often pairs with a hash map.
7️⃣ Subarray Sum Equals K
Problem
Given an integer array and integer k, return the number of subarrays whose sum equals k.
nums = [1, 1, 1], k = 2
answer = 2
Subarrays:
[1, 1] at index 0 to 1
[1, 1] at index 1 to 2
Code
def subarray_sum(nums, k):
count = {0: 1}
current_sum = 0
result = 0
for num in nums:
current_sum += num
need = current_sum - k
if need in count:
result += count[need]
count[current_sum] = count.get(current_sum, 0) + 1
return result
Why Count Starts With {0: 1}
This handles subarrays that start at index 0.
Example:
nums = [3], k = 3
current_sum = 3
need = 0
We need prefix sum 0 to already exist.
👉 Interview Answer
For subarray sum equals k, I maintain a running prefix sum and a hash map of how many times each prefix sum has appeared.
At each index, if current_sum - k appeared before, then every occurrence of that previous prefix forms a subarray ending here with sum k.
I initialize the map with {0: 1} to handle subarrays starting at index zero.
8️⃣ Why Sliding Window May Not Work Here
Important Difference
For subarray sum equals k, numbers can be negative.
Example:
nums = [1, -1, 1], k = 1
Sliding window depends on monotonic behavior:
expand right → sum increases
shrink left → sum decreases
But with negative numbers, this is not true.
Prefix Sum Works
Prefix sum does not require positive numbers.
It only relies on:
current_sum - previous_sum = subarray_sum
👉 Interview Answer
If the array may contain negative numbers, sliding window is usually not reliable for subarray sum equals k.
Sliding window needs monotonic behavior, but negative numbers break that.
Prefix sum with a hash map works because it is based on differences between prefix sums, not monotonic movement.
9️⃣ Prefix Sum With Hash Map
Common Pattern
count = {0: 1}
current_sum = 0
answer = 0
for num in nums:
current_sum += num
answer += count.get(current_sum - target, 0)
count[current_sum] = count.get(current_sum, 0) + 1
What The Hash Map Stores
key: prefix sum value
value: how many times this prefix sum has appeared
Why Frequency Matters
The same prefix sum can appear multiple times.
Each occurrence may form a valid subarray.
👉 Interview Answer
In prefix-sum-with-hash-map problems, the map stores the frequency of prefix sums seen so far.
When the current prefix sum is current_sum, we check how many previous prefix sums equal current_sum - target.
Each such previous prefix corresponds to one valid subarray ending at the current index.
🔟 Continuous Subarray Sum
Problem Pattern
Sometimes we need to check whether a subarray sum is divisible by k.
That means:
subarray_sum % k == 0
Using prefix sums:
(prefix[j] - prefix[i]) % k == 0
This implies:
prefix[j] % k == prefix[i] % k
Code
def check_subarray_sum(nums, k):
remainder_index = {0: -1}
current_sum = 0
for i, num in enumerate(nums):
current_sum += num
remainder = current_sum % k
if remainder in remainder_index:
if i - remainder_index[remainder] >= 2:
return True
else:
remainder_index[remainder] = i
return False
Key Insight
If two prefix sums have the same remainder modulo k, their difference is divisible by k.
👉 Interview Answer
For subarray sum divisible by k, I use prefix sum remainders.
If two prefix sums have the same remainder when divided by k, then the subarray between them has sum divisible by k.
I store the earliest index for each remainder to check the required subarray length.
1️⃣1️⃣ Find Pivot Index
Problem
Find an index where the left sum equals the right sum.
nums = [1, 7, 3, 6, 5, 6]
answer = 3
At index 3:
left sum = 1 + 7 + 3 = 11
right sum = 5 + 6 = 11
Code
def pivot_index(nums):
total = sum(nums)
left_sum = 0
for i, num in enumerate(nums):
right_sum = total - left_sum - num
if left_sum == right_sum:
return i
left_sum += num
return -1
Prefix Sum View
left_sum = sum before i
right_sum = total - left_sum - nums[i]
👉 Interview Answer
Pivot index is a prefix-sum style problem.
I keep the running left sum and compute the right sum as total minus left sum minus the current value.
If both sides are equal, the current index is the pivot.
1️⃣2️⃣ Product Except Self Relationship
Why It Is Related
Product except self is not prefix sum, but it uses similar prefix reasoning.
Instead of cumulative sums, it uses:
prefix product
suffix product
For each index:
answer[i] = product before i * product after i
Code
def product_except_self(nums):
n = len(nums)
answer = [1] * n
prefix = 1
for i in range(n):
answer[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer
👉 Interview Answer
Product except self is not exactly prefix sum, but it uses the same idea of storing information before and after each index.
We compute prefix product from the left and suffix product from the right.
Then each answer is prefix product times suffix product.
1️⃣3️⃣ Difference Array
Relationship With Prefix Sum
Difference array is the reverse idea of prefix sum.
Prefix sum answers range queries quickly.
Difference array applies range updates quickly.
Range Update Problem
Suppose we want to add val to every element from left to right.
Instead of updating every element:
for i in range(left, right + 1):
nums[i] += val
Use difference array:
diff[left] += val
diff[right + 1] -= val
Then recover final values using prefix sum.
Code
def range_updates(n, updates):
diff = [0] * (n + 1)
for left, right, val in updates:
diff[left] += val
if right + 1 < len(diff):
diff[right + 1] -= val
result = [0] * n
running = 0
for i in range(n):
running += diff[i]
result[i] = running
return result
👉 Interview Answer
Difference array is closely related to prefix sum.
Prefix sum is useful for fast range queries.
Difference array is useful for fast range updates.
We mark changes at the boundaries and then use a prefix sum pass to reconstruct the final array.
1️⃣4️⃣ Two-Dimensional Prefix Sum
Problem
Given a matrix, answer region sum queries.
sum of rectangle from (row1, col1) to (row2, col2)
Build Formula
Use an extra row and column of zeros.
prefix[r + 1][c + 1]
= matrix[r][c]
+ prefix[r][c + 1]
+ prefix[r + 1][c]
- prefix[r][c]
Query Formula
sumRegion(row1, col1, row2, col2)
= prefix[row2 + 1][col2 + 1]
- prefix[row1][col2 + 1]
- prefix[row2 + 1][col1]
+ prefix[row1][col1]
Code
class NumMatrix:
def __init__(self, matrix):
if not matrix or not matrix[0]:
self.prefix = [[0]]
return
rows = len(matrix)
cols = len(matrix[0])
self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
self.prefix[r + 1][c + 1] = (
matrix[r][c]
+ self.prefix[r][c + 1]
+ self.prefix[r + 1][c]
- self.prefix[r][c]
)
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]
)
👉 Interview Answer
For 2D prefix sum, I use an extra top row and left column of zeros to simplify boundaries.
Each prefix cell stores the sum of the rectangle from the top-left corner to that cell.
A region sum can then be computed by inclusion-exclusion using four prefix values.
1️⃣5️⃣ Inclusion-Exclusion in 2D Prefix Sum
Why We Subtract and Add Back
For rectangle query:
target rectangle
= big rectangle
- area above
- area left
+ overlapping area removed twice
Formula
result
= bottom_right
- above
- left
+ overlap
Visual Reasoning
A = total area from origin to bottom-right
B = area above target
C = area left of target
D = overlap of B and C
target = A - B - C + D
👉 Interview Answer
The 2D prefix sum query uses inclusion-exclusion.
We start with the large rectangle from the origin to the bottom-right corner.
Then we subtract the area above and the area to the left.
Since the top-left overlap was subtracted twice, we add it back once.
1️⃣6️⃣ Prefix Sum vs Sliding Window
Prefix Sum
Works well when:
- Need arbitrary range sums
- Need repeated queries
- Numbers can be negative
- Need count of subarrays with exact sum
- Need hash map of previous prefix sums
Sliding Window
Works well when:
- Need contiguous window
- Condition is monotonic
- Usually positive numbers
- Need longest or shortest valid window
- Can expand and shrink safely
Example Difference
| Problem | Better Pattern | Reason |
|---|---|---|
| Subarray sum equals k with negatives | Prefix Sum | No monotonicity |
| Minimum size subarray sum with positives | Sliding Window | Sum grows/shrinks predictably |
| Range sum query immutable | Prefix Sum | Repeated O(1) queries |
| Longest substring without repeats | Sliding Window | Need maintain valid window |
👉 Interview Answer
Prefix sum and sliding window both work with subarrays, but they solve different types of problems.
Prefix sum is better when we need exact range sums, repeated range queries, or when negative numbers are involved.
Sliding window is better when we can maintain a valid window using monotonic expand-and-shrink behavior.
1️⃣7️⃣ Prefix Sum vs Hash Map
Prefix Array
Use when:
Need direct range sum query by index.
Need many immutable range queries.
Example:
sum(left, right)
Prefix Sum + Hash Map
Use when:
Need to count or find subarrays with a target property.
Need to remember previous prefix sums.
Example:
subarray_sum_equals_k
👉 Interview Answer
A prefix array is useful when queries give explicit left and right indexes.
Prefix sum with a hash map is useful when we need to find or count subarrays dynamically.
The hash map lets us check whether a needed previous prefix sum has appeared before.
1️⃣8️⃣ Common Edge Cases
Empty Array
nums = []
Single Element
nums = [k]
Range Starts at Index 0
Handled by:
prefix[0] = 0
or:
count = {0: 1}
Negative Numbers
Prefix sum handles negatives well.
Sliding window may not.
Large Values
In Python this is usually fine.
In languages like Java or C++, consider integer overflow.
k Equals 0
Important in:
subarray sum equals k
subarray sum divisible by k
👉 Interview Answer
The main edge cases are empty input, single-element arrays, ranges starting at index zero, negative numbers, and large sums.
I usually use prefix[0] = 0 or initialize the hash map with {0: 1} to handle subarrays starting at the beginning.
In fixed-width integer languages, I also consider overflow.
1️⃣9️⃣ Complexity Analysis
Prefix Array
Build: O(n)
Range query: O(1)
Space: O(n)
Prefix Sum + Hash Map
Time: O(n)
Space: O(n)
2D Prefix Sum
For an m x n matrix:
Build: O(mn)
Region query: O(1)
Space: O(mn)
👉 Interview Answer
Prefix sum usually trades memory for faster queries.
A one-dimensional prefix array takes O(n) space and supports O(1) range sum queries after O(n) preprocessing.
Prefix sum with a hash map is O(n) time and O(n) space.
Two-dimensional prefix sum takes O(mn) preprocessing and answers each rectangle query in O(1).
2️⃣0️⃣ Common Mistakes
Mistake 1: Off-by-One Error
Wrong formula:
prefix[right] - prefix[left]
Correct formula with n + 1 prefix:
prefix[right + 1] - prefix[left]
Mistake 2: Forgetting Prefix Zero
For subarrays starting at index 0:
count = {0: 1}
Mistake 3: Updating Hash Map Too Early
Correct order:
result += count.get(current_sum - k, 0)
count[current_sum] += 1
If we update first, we may count invalid empty subarrays.
Mistake 4: Using Sliding Window With Negative Numbers
Negative values break monotonic behavior.
Mistake 5: 2D Inclusion-Exclusion Sign Error
Correct pattern:
bottom_right - above - left + overlap
👉 Interview Answer
Common prefix sum mistakes include off-by-one errors, forgetting the initial zero prefix, updating the hash map in the wrong order, using sliding window when negative numbers are present, and making sign mistakes in 2D inclusion-exclusion.
I avoid these by defining exactly what prefix[i] means before writing code.
2️⃣1️⃣ Standard Templates
Prefix Array Template
prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
prefix[i + 1] = prefix[i] + nums[i]
def range_sum(left, right):
return prefix[right + 1] - prefix[left]
Prefix Sum + Hash Map Template
count = {0: 1}
current_sum = 0
answer = 0
for num in nums:
current_sum += num
answer += count.get(current_sum - target, 0)
count[current_sum] = count.get(current_sum, 0) + 1
Prefix Remainder Template
first_index = {0: -1}
current_sum = 0
for i, num in enumerate(nums):
current_sum += num
remainder = current_sum % k
if remainder in first_index:
# check condition
pass
else:
first_index[remainder] = i
2D Prefix Sum Template
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
prefix[r + 1][c + 1] = (
matrix[r][c]
+ prefix[r][c + 1]
+ prefix[r + 1][c]
- prefix[r][c]
)
def region_sum(row1, col1, row2, col2):
return (
prefix[row2 + 1][col2 + 1]
- prefix[row1][col2 + 1]
- prefix[row2 + 1][col1]
+ prefix[row1][col1]
)
🧠 Staff-Level Answer Final
👉 Interview Answer Full Version
Prefix sum is a preprocessing technique that stores cumulative sums so range-sum or subarray-sum problems can be solved efficiently.
The basic idea is that the sum of a subarray can be represented as the difference between two prefix sums.
If prefix[i] stores the sum of elements before index i, then the sum from left to right inclusive is prefix[right + 1] minus prefix[left].
This gives O(1) range sum queries after O(n) preprocessing.
Prefix sum is especially useful when there are many immutable range queries, or when subarray sums can be transformed into differences between current and previous prefix sums.
For problems like subarray sum equals k, I maintain a running current_sum and a hash map of previous prefix sum frequencies.
At each index, I check whether current_sum - k has appeared before. If it has, every occurrence represents a subarray ending at the current index with sum k.
I initialize the map with {0: 1} to handle subarrays starting at index zero.
Prefix sum is also useful for modulo problems. If two prefix sums have the same remainder modulo k, then the subarray between them has sum divisible by k.
For 2D matrix region sum, I use a two-dimensional prefix sum with an extra row and column of zeros. Region queries are answered using inclusion-exclusion: bottom-right minus above minus left plus overlap.
At a senior level, I would also compare prefix sum with sliding window.
Sliding window is good when the condition is monotonic and the window can expand and shrink safely. Prefix sum is better for exact sums, repeated range queries, negative numbers, and counting subarrays using previous prefix states.
The main pitfalls are off-by-one errors, forgetting the zero prefix, updating the hash map in the wrong order, and making inclusion-exclusion mistakes in 2D prefix sum.
The key is to clearly define what prefix[i] means before implementing the formula.
⭐ Final Insight
Prefix Sum 的核心不是简单地存一个累计数组。
它的核心是把 range sum 转化成两个 prefix state 的差。
Senior-level 的重点是：
prefix[i] 到底代表什么， 为什么 range sum 可以用两个 prefix 相减， 为什么 hash map 可以记录 previous prefix states， 以及什么时候 prefix sum 比 sliding window 更合适。
能讲清楚这些，Prefix Sum 就不只是一个公式， 而是一种把区间问题转化成状态差的问题建模方式。
中文部分
🎯 Prefix Sum
1️⃣ 核心框架
讨论 Prefix Sum 时，我通常从：
- 它解决什么问题
- 为什么 prefix sum 可以优化 range query
- 一维 prefix sum
- Prefix sum with hash map
- Subarray sum equals k
- Range sum query
- Difference array 的关系
- 二维 prefix sum
- 常见 edge cases
- 高级工程师解释方式
2️⃣ 要解决什么问题？
Prefix sum 用于高效处理 range sum 或 subarray sum 问题。
它常用于：
- Range sum queries
- Subarray sum equals target
- Count subarrays with certain sum
- Find equilibrium index
- Product except self style reasoning
- Difference array problems
- 2D matrix region sum
- Repeated summation optimization
核心思想是：
提前计算累计和，
让任意区间和可以快速得到。
👉 面试回答
Prefix sum 是一种 preprocessing 技巧。
它提前存储 cumulative sums， 使得任意 subarray 的 sum 可以在 O(1) 时间内计算。
它特别适合 repeated range queries， 或者可以把 subarray sum 转化成两个 prefix sums 差值的问题。
3️⃣ 为什么 Prefix Sum 有效？
暴力解法
如果要计算 index left 到 right 的 sum：
total = 0
for i in range(left, right + 1):
total += nums[i]
每次 query 是：
O(n)
如果 query 很多，就会很慢。
Prefix Sum 优化
构建：
prefix[i] = nums[0] 到 nums[i - 1] 的和
那么：
sum(left, right) = prefix[right + 1] - prefix[left]
Example
nums = [2, 4, 6, 8]
prefix = [0, 2, 6, 12, 20]
index 1 到 3 的 sum：
nums[1] + nums[2] + nums[3]
= 4 + 6 + 8
= 18
用 prefix sum：
prefix[4] - prefix[1]
= 20 - 2
= 18
👉 面试回答
Prefix sum 有效，是因为一个 range sum 可以表示成两个 cumulative sums 的差。
如果 prefix[i] 表示 index i 之前所有元素的和， 那么 left 到 right 的区间和就是 prefix[right + 1] - prefix[left]。
这样就避免了重复计算。
4️⃣ 一维 Prefix Sum
标准构建方式
def build_prefix(nums):
prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
Range Query
def range_sum(prefix, left, right):
return prefix[right + 1] - prefix[left]
为什么用 n + 1 长度？
多放一个开头的 0，可以简化边界。
prefix[0] = 0
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
所有 range sum 都可以用同一个公式：
prefix[right + 1] - prefix[left]
👉 面试回答
我通常会构建长度为 n + 1 的 prefix array， 并让 prefix[0] = 0。
这样 range sum 公式非常干净： left 到 right inclusive 的和就是 prefix[right + 1] - prefix[left]。
这也避免了 range 从 index 0 开始时的特殊处理。
5️⃣ Range Sum Query
Problem
给定数组，回答多次 range sum query。
nums = [1, 3, 5, 7, 9]
sumRange(1, 3) = 3 + 5 + 7 = 15
sumRange(0, 4) = 25
Code
class NumArray:
def __init__(self, nums):
self.prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
self.prefix[i + 1] = self.prefix[i] + nums[i]
def sumRange(self, left, right):
return self.prefix[right + 1] - self.prefix[left]
Complexity
Build: O(n)
Query: O(1)
Space: O(n)
👉 面试回答
对 immutable range sum query， 我会先用 O(n) 构建 prefix sum array。
之后每个 query 都可以用两个 prefix sums 相减，在 O(1) 时间内得到结果。
这是一个典型的用额外空间换查询速度的 trade-off。
6️⃣ Prefix Sum 和 Subarray Sum
核心公式
对于 subarray i 到 j：
sum(i, j) = prefix[j + 1] - prefix[i]
如果我们想要：
sum(i, j) = k
那么：
prefix[j + 1] - prefix[i] = k
变形：
prefix[i] = prefix[j + 1] - k
也就是说：
在当前 prefix sum 下，
我们需要找之前是否出现过 current_sum - k。
👉 面试回答
很多 subarray-sum 问题都可以用 prefix sum 转化。
如果 current_sum 是当前 index 的 prefix sum， 我们想找一个 previous prefix， 使得 current_sum - previous_prefix = k。
那么 previous_prefix 就必须等于 current_sum - k。
所以 prefix sum 经常会搭配 hash map 使用。
7️⃣ Subarray Sum Equals K
Problem
给定整数数组和整数 k，返回 sum 等于 k 的 subarray 数量。
nums = [1, 1, 1], k = 2
answer = 2
Subarrays:
[1, 1] at index 0 to 1
[1, 1] at index 1 to 2
Code
def subarray_sum(nums, k):
count = {0: 1}
current_sum = 0
result = 0
for num in nums:
current_sum += num
need = current_sum - k
if need in count:
result += count[need]
count[current_sum] = count.get(current_sum, 0) + 1
return result
为什么 count 从 {0: 1} 开始？
这是为了处理从 index 0 开始的 subarray。
例如：
nums = [3], k = 3
current_sum = 3
need = 0
我们需要 prefix sum 0 先存在。
👉 面试回答
对 subarray sum equals k， 我维护 running prefix sum， 以及一个 hash map 记录每个 prefix sum 出现过多少次。
对每个位置，如果 current_sum - k 曾经出现过， 那么每一次出现都代表一个以当前位置结尾、sum 为 k 的 subarray。
初始化
{0: 1}是为了处理从 index 0 开始的 subarray。
8️⃣ 为什么这里 Sliding Window 不一定适用？
关键区别
Subarray sum equals k 中，数组可能有 negative numbers。
例如：
nums = [1, -1, 1], k = 1
Sliding window 依赖单调性：
expand right → sum increases
shrink left → sum decreases
但有负数时，这个条件不成立。
Prefix Sum 可以处理
Prefix sum 不依赖正数。
它只依赖：
current_sum - previous_sum = subarray_sum
👉 面试回答
如果数组可能包含 negative numbers， sliding window 通常不适合 subarray sum equals k。
Sliding window 需要单调性， 但 negative numbers 会破坏这种单调性。
Prefix sum with hash map 不依赖单调移动， 它只依赖两个 prefix sums 的差。
9️⃣ Prefix Sum With Hash Map
Common Pattern
count = {0: 1}
current_sum = 0
answer = 0
for num in nums:
current_sum += num
answer += count.get(current_sum - target, 0)
count[current_sum] = count.get(current_sum, 0) + 1
Hash Map 存什么？
key: prefix sum value
value: 这个 prefix sum 出现过多少次
为什么 frequency 重要？
同一个 prefix sum 可能出现多次。
每一次都可能形成一个 valid subarray。
👉 面试回答
在 prefix sum with hash map 问题中， hash map 存的是 previous prefix sum 的 frequency。
当当前 prefix sum 是 current_sum 时， 我们检查 current_sum - target 出现过多少次。
每一次出现都对应一个以当前位置结尾的 valid subarray。
🔟 Continuous Subarray Sum
Problem Pattern
有些题会问 subarray sum 是否能被 k 整除：
subarray_sum % k == 0
使用 prefix sum：
(prefix[j] - prefix[i]) % k == 0
这意味着：
prefix[j] % k == prefix[i] % k
Code
def check_subarray_sum(nums, k):
remainder_index = {0: -1}
current_sum = 0
for i, num in enumerate(nums):
current_sum += num
remainder = current_sum % k
if remainder in remainder_index:
if i - remainder_index[remainder] >= 2:
return True
else:
remainder_index[remainder] = i
return False
核心 Insight
如果两个 prefix sums 对 k 的 remainder 相同， 它们之间的 subarray sum 就可以被 k 整除。
👉 面试回答
对 subarray sum divisible by k， 我会使用 prefix sum remainder。
如果两个 prefix sums 除以 k 的 remainder 相同， 那么它们之间的 subarray sum 就能被 k 整除。
我会记录每个 remainder 最早出现的位置， 用来检查 subarray 长度是否满足要求。
1️⃣1️⃣ Find Pivot Index
Problem
找一个 index，使它左边的 sum 等于右边的 sum。
nums = [1, 7, 3, 6, 5, 6]
answer = 3
index 3:
left sum = 1 + 7 + 3 = 11
right sum = 5 + 6 = 11
Code
def pivot_index(nums):
total = sum(nums)
left_sum = 0
for i, num in enumerate(nums):
right_sum = total - left_sum - num
if left_sum == right_sum:
return i
left_sum += num
return -1
Prefix Sum 视角
left_sum = index i 之前的 sum
right_sum = total - left_sum - nums[i]
👉 面试回答
Pivot index 是一个 prefix-sum 风格的问题。
我维护 running left sum， 然后用 total - left_sum - current value 得到 right sum。
如果 left sum 和 right sum 相等， 当前 index 就是 pivot。
1️⃣2️⃣ Product Except Self Relationship
为什么相关？
Product except self 不完全是 prefix sum， 但它用了类似的 prefix thinking。
不是 cumulative sum，而是：
prefix product
suffix product
对于每个 index：
answer[i] = product before i * product after i
Code
def product_except_self(nums):
n = len(nums)
answer = [1] * n
prefix = 1
for i in range(n):
answer[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer
👉 面试回答
Product except self 不完全是 prefix sum， 但它使用了相同的 prefix/suffix 思路。
我们从左到右计算每个 index 左边的 product， 再从右到左乘上每个 index 右边的 product。
这样每个位置都可以得到 except self 的结果。
1️⃣3️⃣ Difference Array
和 Prefix Sum 的关系
Difference array 可以看作 prefix sum 的反向思路。
Prefix sum 用于快速 range query。
Difference array 用于快速 range update。
Range Update Problem
如果要给 left 到 right 每个元素加 val：
暴力做法：
for i in range(left, right + 1):
nums[i] += val
使用 difference array：
diff[left] += val
diff[right + 1] -= val
最后通过 prefix sum 还原最终数组。
Code
def range_updates(n, updates):
diff = [0] * (n + 1)
for left, right, val in updates:
diff[left] += val
if right + 1 < len(diff):
diff[right + 1] -= val
result = [0] * n
running = 0
for i in range(n):
running += diff[i]
result[i] = running
return result
👉 面试回答
Difference array 和 prefix sum 关系非常紧密。
Prefix sum 适合快速 range query。
Difference array 适合快速 range update。
我们只在区间边界记录变化， 最后用一次 prefix sum pass 还原最终结果。
1️⃣4️⃣ 二维 Prefix Sum
Problem
给定 matrix，回答矩形区域 sum query。
sum of rectangle from (row1, col1) to (row2, col2)
Build Formula
使用额外的一行和一列 0。
prefix[r + 1][c + 1]
= matrix[r][c]
+ prefix[r][c + 1]
+ prefix[r + 1][c]
- prefix[r][c]
Query Formula
sumRegion(row1, col1, row2, col2)
= prefix[row2 + 1][col2 + 1]
- prefix[row1][col2 + 1]
- prefix[row2 + 1][col1]
+ prefix[row1][col1]
Code
class NumMatrix:
def __init__(self, matrix):
if not matrix or not matrix[0]:
self.prefix = [[0]]
return
rows = len(matrix)
cols = len(matrix[0])
self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
self.prefix[r + 1][c + 1] = (
matrix[r][c]
+ self.prefix[r][c + 1]
+ self.prefix[r + 1][c]
- self.prefix[r][c]
)
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]
)
👉 面试回答
对 2D prefix sum， 我会加一行和一列 0 来简化边界处理。
每个 prefix cell 表示从左上角到当前位置的 rectangle sum。
查询某个矩形区域时， 使用 inclusion-exclusion，通过四个 prefix values 计算结果。
1️⃣5️⃣ 2D Prefix Sum 的 Inclusion-Exclusion
为什么要减掉再加回来？
查询矩形时：
target rectangle
= big rectangle
- area above
- area left
+ overlapping area removed twice
Formula
result
= bottom_right
- above
- left
+ overlap
Visual Reasoning
A = origin 到 bottom-right 的总区域
B = target 上方区域
C = target 左边区域
D = B 和 C 的重叠区域
target = A - B - C + D
👉 面试回答
2D prefix sum 查询使用 inclusion-exclusion。
先取从 origin 到 bottom-right 的大矩形。
然后减去 target 上方区域和左边区域。
因为左上角 overlap 被减了两次， 所以需要加回来一次。
1️⃣6️⃣ Prefix Sum vs Sliding Window
Prefix Sum 适合：
- Need arbitrary range sums
- Need repeated queries
- Numbers can be negative
- Need count of subarrays with exact sum
- Need hash map of previous prefix sums
Sliding Window 适合：
- Need contiguous window
- Condition is monotonic
- Usually positive numbers
- Need longest or shortest valid window
- Can expand and shrink safely
Example Difference
| Problem | Better Pattern | Reason |
|---|---|---|
| Subarray sum equals k with negatives | Prefix Sum | No monotonicity |
| Minimum size subarray sum with positives | Sliding Window | Sum grows/shrinks predictably |
| Range sum query immutable | Prefix Sum | Repeated O(1) queries |
| Longest substring without repeats | Sliding Window | Need maintain valid window |
👉 面试回答
Prefix sum 和 sliding window 都可以处理 subarray， 但适用场景不同。
Prefix sum 更适合 exact range sum、repeated range query、negative numbers， 以及通过 previous prefix states 统计 subarray 的问题。
Sliding window 更适合可以安全 expand 和 shrink 的 monotonic window 问题。
1️⃣7️⃣ Prefix Array vs Prefix Sum With Hash Map
Prefix Array
适合：
query 明确给 left 和 right index
需要多次 immutable range sum query
Example:
sum(left, right)
Prefix Sum + Hash Map
适合：
需要动态查找或统计满足 target property 的 subarrays
需要记住 previous prefix sums
Example:
subarray_sum_equals_k
👉 面试回答
Prefix array 适合 query 明确给出 left 和 right 的情况。
Prefix sum with hash map 适合查找或统计 subarray 的情况。
Hash map 可以帮助我们判断某个 needed previous prefix sum 是否出现过。
1️⃣8️⃣ 常见 Edge Cases
Empty Array
nums = []
Single Element
nums = [k]
Range Starts at Index 0
用下面方式处理：
prefix[0] = 0
或者：
count = {0: 1}
Negative Numbers
Prefix sum 可以很好处理 negative numbers。
Sliding window 不一定可以。
Large Values
Python 通常没问题。
Java 或 C++ 要考虑 integer overflow。
k Equals 0
在这些题里要特别注意：
subarray sum equals k
subarray sum divisible by k
👉 面试回答
常见 edge cases 包括 empty input、single element、range 从 index 0 开始、negative numbers 和 large sums。
我通常用 prefix[0] = 0， 或者在 hash map 中初始化
{0: 1}， 来处理从数组开头开始的 subarray。在固定宽度整数语言中，还要注意 overflow。
1️⃣9️⃣ Complexity Analysis
Prefix Array
Build: O(n)
Range query: O(1)
Space: O(n)
Prefix Sum + Hash Map
Time: O(n)
Space: O(n)
2D Prefix Sum
对于 m x n matrix：
Build: O(mn)
Region query: O(1)
Space: O(mn)
👉 面试回答
Prefix sum 通常是用额外空间换更快查询。
一维 prefix array 使用 O(n) space， 在 O(n) preprocessing 后支持 O(1) range sum query。
Prefix sum with hash map 是 O(n) time 和 O(n) space。
二维 prefix sum 是 O(mn) preprocessing， 每次 rectangle query 是 O(1)。
2️⃣0️⃣ 常见错误
Mistake 1: Off-by-One Error
错误公式：
prefix[right] - prefix[left]
使用 n + 1 prefix 时，正确公式是：
prefix[right + 1] - prefix[left]
Mistake 2: 忘记初始 Prefix Zero
处理从 index 0 开始的 subarray：
count = {0: 1}
Mistake 3: Hash Map 更新顺序错误
正确顺序：
result += count.get(current_sum - k, 0)
count[current_sum] += 1
如果先 update，可能会错误计算 empty subarray。
Mistake 4: 对 Negative Numbers 强行用 Sliding Window
Negative values 会破坏 monotonic behavior。
Mistake 5: 2D Inclusion-Exclusion 符号错误
正确模式：
bottom_right - above - left + overlap
👉 面试回答
Prefix sum 常见错误包括 off-by-one、 忘记 initial zero prefix、 hash map 更新顺序错误、 在有 negative numbers 时误用 sliding window、 以及 2D inclusion-exclusion 的符号写错。
我通常会先定义 prefix[i] 的含义，再写公式。
2️⃣1️⃣ 标准模板
Prefix Array Template
prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
prefix[i + 1] = prefix[i] + nums[i]
def range_sum(left, right):
return prefix[right + 1] - prefix[left]
Prefix Sum + Hash Map Template
count = {0: 1}
current_sum = 0
answer = 0
for num in nums:
current_sum += num
answer += count.get(current_sum - target, 0)
count[current_sum] = count.get(current_sum, 0) + 1
Prefix Remainder Template
first_index = {0: -1}
current_sum = 0
for i, num in enumerate(nums):
current_sum += num
remainder = current_sum % k
if remainder in first_index:
# check condition
pass
else:
first_index[remainder] = i
2D Prefix Sum Template
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
prefix[r + 1][c + 1] = (
matrix[r][c]
+ prefix[r][c + 1]
+ prefix[r + 1][c]
- prefix[r][c]
)
def region_sum(row1, col1, row2, col2):
return (
prefix[row2 + 1][col2 + 1]
- prefix[row1][col2 + 1]
- prefix[row2 + 1][col1]
+ prefix[row1][col1]
)
🧠 Staff-Level Answer Final
👉 面试回答完整版本
Prefix sum 是一种 preprocessing technique， 用来高效处理 range sum 和 subarray sum 问题。
它的核心思想是： 一个 subarray 的和可以表示成两个 prefix sums 的差。
如果 prefix[i] 表示 index i 之前所有元素的和， 那么 left 到 right inclusive 的 sum 就是 prefix[right + 1] - prefix[left]。
这样在 O(n) preprocessing 后， 每个 range sum query 可以 O(1) 得到答案。
Prefix sum 特别适合多次 immutable range queries， 也适合把 subarray sum 转化成 current prefix 和 previous prefix 之间差值的问题。
对 subarray sum equals k 这类题， 我会维护 running current_sum， 同时用 hash map 记录 previous prefix sum 的出现次数。
在每个位置， 我检查 current_sum - k 是否出现过。 如果出现过， 每一次出现都对应一个以当前位置结尾、sum 为 k 的 subarray。
我会初始化
{0: 1}， 用来处理从 index 0 开始的 subarray。Prefix sum 也适合 modulo 问题。 如果两个 prefix sums 对 k 的 remainder 相同， 它们之间的 subarray sum 就能被 k 整除。
对 2D matrix region sum， 我会使用二维 prefix sum， 并加额外的一行和一列 0 来简化边界。 查询矩形区域时使用 inclusion-exclusion： bottom-right minus above minus left plus overlap。
高级工程师层面， 我还会比较 prefix sum 和 sliding window。
Sliding window 适合 condition 有单调性， 可以安全 expand 和 shrink 的问题。
Prefix sum 更适合 exact sums、repeated range queries、negative numbers， 以及需要通过 previous prefix states 统计 subarray 的问题。
常见陷阱包括 off-by-one、 忘记 zero prefix、 hash map 更新顺序错误、 以及 2D prefix sum inclusion-exclusion 符号错误。
实现前最重要的是先定义清楚： prefix[i] 到底表示什么。
⭐ Final Insight
Prefix Sum 的核心不是“累计和数组”。
它的核心是把区间问题转化成两个状态的差。
Senior-level 的重点是：
prefix[i] 的定义是什么， range sum 为什么等于两个 prefix 相减， hash map 为什么可以记录 previous prefix states， 以及什么时候 prefix sum 比 sliding window 更可靠。
能讲清楚这些， Prefix Sum 就是一个非常强的区间问题建模工具。
Implement