Drag across the tally. Click it, then use ← → to step and Space to play.
Precompute running totals once, so any range sum is a single subtraction: the total up to R, minus the total before L. One O(n) pass, then every query is O(1). Add a hash map of the prefix sums seen so far and you can also count subarrays with a given sum: a subarray ending here sums to k exactly when some earlier prefix equals (current prefix − k).
FIG. 14 · The array is the top row. The prefix row sits half a slot to the left, so prefix[i] lines up with the gap between nums[i − 1] and nums[i]: it is the total of everything to its left. A range L..R is framed in red, with the two brackets above it showing the prefix up to R and the prefix before L; the range is their difference. The running values are listed on the right.
class PrefixSum:
def __init__(self, nums):
self.prefix = [0]
for x in nums:
self.prefix.append(self.prefix[-1] + x)
def range_sum(self, L, R): # sum of nums[L..R]
return self.prefix[R + 1] - self.prefix[L]
def subarray_sum(nums, k): # count subarrays summing to k
count = {0: 1}
cur = res = 0
for x in nums:
cur += x
res += count.get(cur - k, 0)
count[cur] = count.get(cur, 0) + 1
return res
def pivotIndex(nums): # LeetCode 724
total = sum(nums)
left = 0 # prefix sum before i
for i, x in enumerate(nums):
if left == total - left - x:
return i # left side == right side
left += x
return -1
def productExceptSelf(nums): # LeetCode 238
n = len(nums)
res = [1] * n
pre = 1
for i in range(n):
res[i] = pre # product of everything to the left
pre *= nums[i]
suf = 1
for i in range(n - 1, -1, -1):
res[i] *= suf # times everything to the right
suf *= nums[i]
return res
nums = [1, 7, 3, 6, 5, 6]. Find i where the sum to its left equals the sum to its right. Keep the prefix (left) sum; the right side is total − left − nums[i]. Answer: 3 (1 + 7 + 3 = 11 = 5 + 6).
nums = [1, 2, 3, 4], no division. The answer at i is the product of everything left of i times everything right of i: a prefix product on the way forward, a suffix product on the way back. Answer: [24, 12, 8, 6].
| Operation | Time | Space | Why |
|---|---|---|---|
| Build the prefix row | O(n) | O(n) | One addition per element; n + 1 numbers stored. |
| Each range query | O(1) | — | prefix[R + 1] − prefix[L]. Summing with a loop would be O(R − L + 1) per query. |
| Count subarrays summing to k | O(n) | O(n) | One pass with a dict of prefix counts, instead of O(n²) subarrays. |
prefix[0] = 0 is the sum of nothing. It lets range_sum(0, R) be prefix[R + 1] − prefix[0] with no special case, and in subarray_sum, count = {0: 1} is the same idea: it lets a subarray that starts at index 0 be found.
"Subarray sum equals k" looks like a window problem, but a window only works when growing it always increases the sum (all positive numbers). With negatives, shrinking can make the sum go up, and the window doesn't know which way to move. The prefix-sum map doesn't care about signs.
Build once in O(n), answer each in O(1).
Look up cur − k among the prefixes seen so far.
class PrefixSum:
def __init__(self, nums):
self.prefix = [0]
for x in nums:
self.prefix.append(self.prefix[-1] + x)
def range_sum(self, L, R): # sum of nums[L..R]
return self.prefix[R + 1] - self.prefix[L]
def subarray_sum(nums, k): # count subarrays summing to k
count = {0: 1}
cur = res = 0
for x in nums:
cur += x
res += count.get(cur - k, 0)
count[cur] = count.get(cur, 0) + 1
return res