What partial sums are
A partial sum (also called a prefix sum) is the sum of the first few elements of a list. For the list [3, 1, 4, 1, 5, 9, 2, 6] the partial sums are 3, then 3 + 1 = 4, then 4 + 4 = 8, and so on:
numbers: 3 1 4 1 5 9 2 6
partial: 3 4 8 9 14 23 25 31
Each partial sum is the one before it plus the next number. Computing all of them takes one pass over the list.
The problem partial sums solve
Suppose you must answer many questions of the form "what is the sum of the elements from index l to index r?" The direct way is sum(nums[l:r + 1]). That is O(r - l + 1) for each question, so with q questions on a list of n numbers the worst case is O(n * q).
With partial sums prepared once, each question takes O(1). The preparation is a single O(n) pass.
Building the prefix array in Python
The usual trick is to make the prefix list one element longer than the input, with a leading 0. Then prefix[i] is the sum of the first i elements, and prefix[0] is the sum of none of them:
nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
print(prefix) # [0, 3, 4, 8, 9, 14, 23, 25, 31]
The standard library has a shortcut. itertools.accumulate yields running totals, and its initial argument puts the leading 0 in front:
from itertools import accumulate
prefix = list(accumulate(nums, initial=0))
print(prefix) # [0, 3, 4, 8, 9, 14, 23, 25, 31]
Without initial, accumulate returns the list without the leading 0, so the first value is 3.
Answering a range query
The sum of nums[l] through nums[r], both included, is the total of the first r + 1 elements minus the total of the first l elements:
def range_sum(prefix, l, r):
return prefix[r + 1] - prefix[l]
print(range_sum(prefix, 2, 5)) # 4 + 1 + 5 + 9 = 19
print(range_sum(prefix, 0, 7)) # 31, the whole list
print(range_sum(prefix, 3, 3)) # 1, a single element
The leading 0 is what makes l = 0 work without a special case: prefix[0] is 0, so nothing is subtracted.
Common uses
- Many range sums. As above: prepare once, then answer each query in O(1).
- Counting subarrays with a given sum. A subarray from
ltorhas sumkexactly whenprefix[r + 1] - prefix[l] == k. While scanning, a dictionary of the prefix values seen so far lets you count the matching starts in O(1) per element:
def count_k(nums, k):
seen = {0: 1}
total = 0
result = 0
for x in nums:
total += x
result += seen.get(total - k, 0)
seen[total] = seen.get(total, 0) + 1
return result
print(count_k([1, 1, 1], 2)) # 2
print(count_k([1, 2, 3], 3)) # 2
- Two dimensions. For a grid,
P[i + 1][j + 1]can hold the sum of the rectangle from the top-left corner to cell(i, j), built asgrid[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j]. Any rectangle sum then needs four lookups.
Common mistakes
- Off-by-one in the formula. With a leading 0, the sum of indexes
ltorinclusive isprefix[r + 1] - prefix[l]. Usingprefix[r] - prefix[l]leaves out the last element. - Forgetting the leading 0. Without it, queries that start at index 0 need a special case.
- Changing the list after building the prefix array. The prefix values do not update themselves. If elements change often, a different structure is needed.
- Recomputing with
sum()in a loop. Callingsum(nums[:i])for everyigives O(n²) time in total, while one running total gives O(n).
Key takeaways
- A partial sum is a running total, computed in one O(n) pass.
- In Python,
list(accumulate(nums, initial=0))builds the prefix list with the leading 0. - The sum of
nums[l..r]isprefix[r + 1] - prefix[l], an O(1) query. - The idea carries over to counting subarrays with a given sum and to sums over rectangles in a grid.
