Prefix sums
In one line
Precompute running totals once in O(n) so the sum of any range is a single subtraction in O(1).
What it is
A prefix sum array stores, at position i, the total of all elements before i. With prefix[0] = 0 and prefix[i + 1] = prefix[i] + nums[i], the sum of nums[l..r] (inclusive) is prefix[r + 1] - prefix[l].
The idea extends in three common ways: combined with a hash map to count subarrays with a given sum, to two dimensions to get any rectangle's sum in O(1), and in reverse as a difference array to apply many range updates cheaply.
Why interviewers ask
Range-sum and 'count subarrays with sum k' questions are interview staples. A brute force that re-adds each range costs O(n) per query or O(n^2) overall; prefix sums cut that to O(1) per query. Interviewers look for the off-by-one-safe n + 1 layout, and for the insight that a subarray sum is the difference of two prefix sums, which is what unlocks the hash map version.
How it works
- 1Allocate prefix of length n + 1 with prefix[0] = 0, which represents the empty prefix.
- 2One pass: prefix[i + 1] = prefix[i] + nums[i]. O(n) time.
- 3Range query: sum(nums[l..r]) = prefix[r + 1] - prefix[l]. Everything before l cancels out. O(1).
- 4Count subarrays summing to k: a subarray ending at j sums to k exactly when some earlier prefix equals running - k. Keep a hash map from prefix value to how many times it has appeared, starting with {0: 1}.
- 52D version: S[r + 1][c + 1] = grid[r][c] + S[r][c + 1] + S[r + 1][c] - S[r][c]. A rectangle sum is then four lookups combined by inclusion-exclusion.
- 6Difference array (the reverse): to add v to every element in [l, r], do diff[l] += v and diff[r + 1] -= v; after all updates, one prefix sum over diff gives the final array.
Worked example · Range sums and 'subarray sum equals k'
- nums = [3, 1, 4, 1, 5]. prefix = [0, 3, 4, 8, 9, 14].
- Sum of nums[1..3] = prefix[4] - prefix[1] = 9 - 3 = 6. Check: 1 + 4 + 1 = 6.
- Sum of nums[0..4] = prefix[5] - prefix[0] = 14. The leading 0 is what makes ranges starting at index 0 work.
- Now count subarrays of nums = [1, 2, 3] that sum to k = 3. Start seen = {0: 1}, running = 0, count = 0.
- x = 1: running = 1. Look for 1 - 3 = -2: none. seen = {0: 1, 1: 1}.
- x = 2: running = 3. Look for 3 - 3 = 0: found once, count = 1 (subarray [1, 2]). seen = {0: 1, 1: 1, 3: 1}.
- x = 3: running = 6. Look for 6 - 3 = 3: found once, count = 2 (subarray [3]). Answer 2, found in one pass.
Picture it
Think of the odometer in a car. To know how far you drove between the second and fifth stop, you do not re-drive the route; you subtract the odometer reading at the second stop from the reading at the fifth. A prefix sum array is the odometer for your data.
Reference code
def build_prefix(nums):
prefix = [0] * (len(nums) + 1) # prefix[i] = sum of nums[:i]
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
return prefix
def range_sum(prefix, l, r): # sum of nums[l..r], inclusive
return prefix[r + 1] - prefix[l]
def subarray_sum_equals_k(nums, k):
count = 0
running = 0
seen = {0: 1} # the empty prefix has sum 0
for x in nums:
running += x
count += seen.get(running - k, 0)
seen[running] = seen.get(running, 0) + 1
return count
build_prefix uses the n + 1 layout so range_sum needs no special case for l = 0. subarray_sum_equals_k counts subarrays ending at each position whose sum is k by looking up how many earlier prefixes equal running - k; it works with negative numbers, where a sliding window does not. O(n) time and O(n) space.
Key patterns
Static range sum queries
When: Many sum queries on an array that does not change
How: Build prefix once in O(n); answer each query as prefix[r + 1] - prefix[l] in O(1).
Prefix sum + hash map
When: Count or find subarrays with sum exactly k, including with negative numbers
How: Track running sum; add seen[running - k] to the answer; then record running in seen. Start with {0: 1}.
Prefix of transformed values
When: Equal numbers of 0s and 1s, or subarrays divisible by k
How: Map 0 to -1 and look for repeated prefix sums, or store prefix mod k and look for equal remainders.
Prefix and suffix products
When: Product of array except self without division
How: answer[i] = product of everything left of i times product of everything right of i, built in two passes.
Difference array
When: Many range updates followed by reading the final array (booking counts, flight seats)
How: diff[l] += v, diff[r + 1] -= v per update, then one prefix pass. O(n + q) instead of O(n * q).
Real-world use
Integral images in computer vision
The Viola-Jones face detector, long used in OpenCV and early camera face detection, builds a 2D prefix sum (summed-area table) so the sum of any rectangle of pixels takes four lookups, letting it test thousands of rectangle features per frame.
Monitoring counters
Prometheus counters only ever go up (total requests served). Queries like rate() and increase() compute traffic in a time window as the difference of two cumulative values, the same idea as prefix[r + 1] - prefix[l].
SQL running totals
Analytics queries use SUM(amount) OVER (ORDER BY day) in PostgreSQL, BigQuery or Snowflake to produce running totals; reports then subtract two running totals to get the total for any date range.
Fenwick trees for leaderboards and ranking
When values change often, a Fenwick (binary indexed) tree keeps prefix sums updatable in O(log n). It is used in competitive programming and in ranking systems to answer 'how many scores are below x' quickly.
In a project
A fitness app shows users their total steps for any custom date range (last 7 days, this month, a chosen week) across years of daily data, and the endpoint is slow because it adds up rows on every request.
- Store a cumulative step total per user per day (the prefix sum) alongside the daily count, updated in O(1) when each day's data arrives.
- Answer any range query as cumulative[end] - cumulative[start - 1], two point lookups instead of summing up to 365+ rows.
- For 'days when steps over any 7-day window hit a goal', slide over the prefix array computing each window in O(1).
- Handle late corrections to a past day by recomputing the cumulative values from that day forward, or move to a Fenwick tree if corrections are frequent.
Impact: The range endpoint goes from a database scan of hundreds of rows to two indexed reads, cutting latency from tens of milliseconds to a few and removing load from the database during peak hours.
Trade-offs
Use it when
- Many range-sum queries on data that rarely changes
- Counting subarrays with an exact sum, especially with negative numbers
- Applying many range updates before a single read (difference array)
Avoid it when
- Values change between queries: each update costs O(n) to rebuild; use a Fenwick tree or segment tree for O(log n)
- You need range minimum or maximum: subtraction does not undo a min, so use a sparse table or segment tree
- All numbers are positive and you want the longest or shortest window with a sum condition: a sliding window uses O(1) space
Cost: Build O(n) time and O(n) space; each range query O(1). Prefix + hash map counting: O(n) time, O(n) space. 2D: build O(R * C), query O(1).
Common mistakes
- Using a length-n prefix array and then mishandling ranges that start at index 0; the n + 1 layout with a leading 0 avoids this.
- Forgetting to seed the hash map with {0: 1}, which misses subarrays that start at index 0.
- Updating the map before looking up running - k, which can count an empty subarray when k = 0.
- Reaching for a sliding window on arrays with negative numbers; the window sum is not monotonic, so prefix sums with a hash map are needed.
- Getting the 2D inclusion-exclusion signs wrong; draw the four rectangles before coding.
Interview questions
Quick revision
- prefix[0] = 0; prefix[i + 1] = prefix[i] + nums[i].
- sum(l..r) = prefix[r + 1] - prefix[l].
- Subarray sum = k: count += seen[running - k]; seed seen = {0: 1}.
- Works with negatives (sliding window does not).
- 2D: inclusion-exclusion with four corners.
- Difference array: diff[l] += v, diff[r + 1] -= v, then prefix-sum it.
- Frequent updates: Fenwick or segment tree, O(log n).
- Build O(n), query O(1), space O(n).
Check yourself
1. With prefix of length n + 1 and prefix[0] = 0, what is the sum of nums[2..5] inclusive?
2. Why is the hash map seeded with {0: 1} when counting subarrays with sum k?
3. For nums = [2, -1, 2] and k = 2, how many subarrays sum to k?
4. Which problem is plain prefix sums NOT good for?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.