Prefix SumPrefix sums
Accumulate once, and a range sum becomes a single subtraction.
Used for: Range totals in reports, subarray-sum problems
01Why it exists
One revenue figure per day, and management asks for the total over some arbitrary range at any moment, hundreds of times a day. Adding it up from scratch every time gets slow as soon as the data grows.
Why this fitsSpend O(n) once to compute the running total from day one up to each day, and from then on any range is the difference between two of those totals: O(1).
Count the contiguous subarrays whose sum equals k. Brute-forcing every (l, r) is O(n²), which falls apart once n reaches a hundred thousand.
Why this fitsA range sum is the difference of two prefix sums. On reaching position j, the only question is how many earlier prefix sums equal P[j] − k, and a hash table of counts answers it — O(n) overall.
The integral image is a staple of computer vision: you need the pixel total of any rectangular region of a picture, quickly, for face detection and blur filters.
Why this fitsA 2D prefix sum. Build the table once in O(mn), and afterwards any rectangle's total is four values added and subtracted, O(1).
Reach for it when you see:Range sums, the sum of a contiguous subarray, repeated queries against data that never changes, the total over a rectangular region, a sum equal to k.
02The core idea
A prefix sum is the array of running totals from the start up to each position: P[i] = a[0] + a[1] + … + a[i-1], with one spare slot so that P[0] = 0. The sum of any range a[l..r] is then P[r+1] − P[l]: the total up to r, minus the total before l, leaving exactly the stretch in between.
It is the simplest form of trading preprocessing for query speed: build the table once in O(n), and every query afterwards is O(1). The precondition is that the data does not change, because altering a single a[i] would force every later P to be updated. If the data is updated as often as it is queried, you need to step up to a Fenwick tree or a segment tree, which belong to the chapter on trees.
That spare P[0] = 0 slot matters more than it looks: it removes the need to special-case a range that starts at 0. The same idea extends in several directions — prefix maximums, prefix XOR, prefix products (Product of Array Except Self is a prefix product multiplied by a suffix product) — and all it takes is an operation that either has an inverse or only ever needs to accumulate one way.
03The algorithm
- 1Allocate an array of length
n + 1withP[0] = 0. - 2Sweep left to right with
P[i+1] = P[i] + a[i]. Each step is a single addition, so building the table is O(n). - 3To query the sum of
a[l..r], returnP[r+1] − P[l]. Note the right edge is r+1, because P is defined to exclude its own position. - 4When the question is "how many subarrays sum to k", rewrite it as
P[j] − P[i] = kand, as you scan, keep a hash table counting how often each prefix sum has appeared; at j, look up how many timesP[j] − khas occurred. Remember to seed it with{0: 1}. - 5In two dimensions,
S[r+1][c+1] = grid[r][c] + S[r][c+1] + S[r+1][c] − S[r][c](inclusion-exclusion: add the left and the top, then subtract the top-left corner counted twice), and a rectangle query is the same four terms added and subtracted.
04Interactive demo
Press "Build one step" to watch P accumulate one cell at a time; once the table is built, choose l and r to see how a range sum falls out of subtracting one P value from another.
05Code
Three parts: the basic build and query, prefix sums plus a hash table for counting subarrays, and the 2D prefix sum. The C++ version stores the prefix sums as long long so the running total cannot overflow.
# Build in O(n): P[i] = a[0] + ... + a[i-1], with one spare slot so P[0] = 0
def build_prefix(a):
p = [0] * (len(a) + 1)
for i, x in enumerate(a):
p[i + 1] = p[i] + x
return p
# Query in O(1): the sum of a[l..r]
def range_sum(p, l, r):
return p[r + 1] - p[l]
a = [3, 1, 4, 1, 5, 9, 2, 6]
p = build_prefix(a) # [0, 3, 4, 8, 9, 14, 23, 25, 31]
range_sum(p, 2, 5) # 4+1+5+9 = 19 = p[6] - p[2]
# Prefix sums + a hash table: how many subarrays sum to exactly k (LeetCode 560)
# sum of the subarray (i, j] = P[j] - P[i] = k ⇔ P[i] = P[j] - k
# so on reaching j, ask how many earlier prefix sums equal P[j] - k
def subarray_sum(nums, k):
count = 0
seen = {0: 1} # prefix sum 0 has already occurred once (the empty prefix)
running = 0
for x in nums:
running += x
count += seen.get(running - k, 0)
seen[running] = seen.get(running, 0) + 1
return count
# 2D prefix sums: S[r][c] is the total of the rectangle from the top-left corner to (r-1, c-1)
def build_2d(grid):
m, n = len(grid), len(grid[0])
s = [[0] * (n + 1) for _ in range(m + 1)]
for r in range(m):
for c in range(n):
s[r+1][c+1] = grid[r][c] + s[r][c+1] + s[r+1][c] - s[r][c]
return s
def rect_sum(s, r1, c1, r2, c2): # top-left (r1,c1) to bottom-right (r2,c2)
return s[r2+1][c2+1] - s[r1][c2+1] - s[r2+1][c1] + s[r1][c1]06Practice
- LeetCode 303Range Sum Query - ImmutableEasy
- LeetCode 724Find Pivot IndexEasy
- LeetCode 560Subarray Sum Equals K (prefix sums plus a hash table)Medium
- LeetCode 304Range Sum Query 2D - ImmutableMedium
- LeetCode 974Subarray Sums Divisible by KMedium