What you will learn
- Building prefix sums and answering range sums in O(1).
- Combining prefix sums with a hash map to count subarrays.
- Prefix and suffix passes for “everything except me” problems.
Signals
- Many queries for the sum of a range.
- “Number of subarrays whose sum equals k” (especially with negative numbers, where sliding window fails).
- “Product/sum of all elements except index i” without division.
The idea
pre[i] is the sum of the first i elements, with pre[0] = 0. Then sum(nums[l..r]) = pre[r + 1] - pre[l]. The extra leading zero removes all edge cases at index 0.
For counting: a subarray ending at the current index sums to k exactly when some earlier prefix equals running - k. Count earlier prefixes in a dictionary.
Code
"""Prefix sums: O(1) range queries and counting subarrays with a hash map."""
from collections import defaultdict
from itertools import accumulate
class RangeSum:
def __init__(self, nums):
self.pre = [0, *accumulate(nums)] # pre[i] = sum of nums[:i]
def query(self, left, right): # inclusive
return self.pre[right + 1] - self.pre[left]
def count_subarrays_with_sum(nums, k):
count, running = 0, 0
seen = defaultdict(int)
seen[0] = 1 # the empty prefix
for x in nums:
running += x
count += seen[running - k] # earlier prefixes that leave exactly k
seen[running] += 1
return count
def product_except_self(nums):
n = len(nums)
out = [1] * n
left = 1
for i in range(n):
out[i] = left
left *= nums[i]
right = 1
for i in range(n - 1, -1, -1):
out[i] *= right
right *= nums[i]
return out
if __name__ == "__main__":
rs = RangeSum([3, -2, 5, 1, 6])
print(rs.query(1, 3), rs.query(0, 4))
print(count_subarrays_with_sum([1, 2, 3, -3, 1, 2], 3))
print(product_except_self([1, 2, 3, 4]))
Output:
4 13
6
[24, 12, 8, 6]
query(1, 3)is-2 + 5 + 1 = 4.seen[0] = 1accounts for subarrays that start at index 0.- Product except self makes a left-to-right pass of running products, then multiplies in a right-to-left pass. O(n) time, O(1) extra space besides the output.
Variants
- 2D prefix sums:
pre[r][c]for sub-rectangle sums with inclusion-exclusion. - Difference arrays: add
vto a range in O(1) bydiff[l] += v; diff[r+1] -= v, then prefix-sum once. - Prefix XOR or prefix counts of parity work the same way as sums.
- Longest subarray with sum k: store the first index of each prefix instead of counts.
Practise: prefix sum problems.
Key takeaways
pre[r + 1] - pre[l]gives any range sum in O(1) after O(n) setup.- Prefix sum + hash map counts subarrays with a given sum, negative numbers included.
- Initialise the map with prefix 0 to count subarrays starting at index 0.
- Prefix and suffix passes replace division in “except self” problems.
Exercises
- Implement a 2D
RangeSumfor sub-rectangle queries. - Count subarrays whose sum is divisible by k (hint: store prefix mod k).
- Find the longest subarray with equal numbers of 0s and 1s (treat 0 as −1).
Quiz
- Why does
prehave a leading 0? - Why can’t the sliding window pattern count subarrays with sum k when numbers can be negative?
- What does a difference array speed up?
Show answers
- So a range starting at index 0 needs no special case:
pre[r + 1] - pre[0]. - Window validity isn’t monotonic: adding a negative number can bring an oversized sum back to k, so shrinking decisions can be wrong.
- Many range updates: each update is O(1), and one prefix pass at the end applies them all.