Precompute running totals once, answer any range-sum in O(1) — plus the hash-map trick for subarray-sum counting and the difference array for bulk range updates.
0 of 5 lessons checked off
Introduction
What it is
A prefix-sum array stores cumulative totals: prefix[i] = sum of the first i elements (with prefix[0] = 0). Any range sum collapses to one subtraction: sum(l..r) = prefix[r+1] − prefix[l].
Its mirror image, the difference array, makes RANGE UPDATES O(1) (add v to diff[l], subtract at diff[r+1]) with a final prefix pass to materialise values.
Why it matters
Many-queries-over-static-data is a constant interview setup: O(n) preprocessing turning every query O(1) beats O(n) per query the moment queries repeat.
The hash-map extension — counting prefix values seen so far — solves 'count subarrays with sum k' in one pass, INCLUDING negative numbers where sliding windows break.
How it works
Build: one pass, prefix[i+1] = prefix[i] + nums[i]. The leading zero kills the l = 0 edge case.
Query: two lookups and a subtraction.
Subarray-sum-k: while scanning, ask 'how many earlier prefixes equal current − k?' — each is a subarray ending here.
Where it's used
Analytics dashboards answering arbitrary date-range totals, image integral tables (2-D prefix sums) in computer vision, checkpointing in stream processing.
In interviews
Range sum query (immutable), subarray sum equals K, contiguous array (equal 0s/1s), product of array except self (prefix products), corporate flight bookings (difference array).
Analogy: A car's odometer: to measure any trip you don't re-drive it — subtract the start reading from the end reading. Prefix sums install an odometer on your array.
Interactive diagram
prefix[r+1] − prefix[l]: two array reads replace re-adding the range.
nums
3
1
4
1
5
9
prefix
0
·
·
·
·
·
·
Seed the prefix array
prefix[0] = 0 represents 'sum of nothing'. The extra leading zero removes an edge case for queries starting at index 0.
1 / 8
Lessons in this topic
Check off lessons as you go — your progress is saved in this browser.
Building and querying prefix sums
The leading zero, off-by-one discipline, O(1) range sums.
Mutable arrays invalidate the table — updates need a Fenwick/segment tree (name it).
Common mistakes
prefix[r] − prefix[l] (off by one on the inclusive right).
Rebuilding the prefix per query, which un-buys the whole trade.
Count subarrays summing to k (prefix + hash map)
A subarray (i..j] sums to k exactly when prefix[j] − prefix[i] = k — so count earlier prefixes equal to current − k.
Count subarrays summing to k (prefix + hash map)
1fromcollectionsimportdefaultdict234defsubarray_sum_count(nums:list[int],k:int)->int:5"""Howmanycontiguoussubarrayssumtok.O(n)/O(n).6Workswithnegatives—whereslidingwindowscannot."""7seen:defaultdict[int,int]=defaultdict(int)8seen[0]=1# empty prefix: subarrays starting at 09running=010count=011forxinnums:12running+=x13count+=seen[running-k]# each match ends a k-sum subarray here14seen[running]+=1# record AFTER counting15returncount
Time: O(n)Space: O(n)
Edge cases
seen[0] = 1 is mandatory — it counts subarrays beginning at index 0.
Negatives and zeros are fine; multiple matches per step are all counted.
Record the current prefix AFTER querying, or a zero-length subarray sneaks in when k = 0.
Common mistakes
Omitting the {0: 1} seed (undercounts by every prefix that itself equals k).
Reaching for a sliding window because 'sum' appeared — negatives void the window logic; this is the correct tool.
Difference array (bulk range updates)
Store deltas at boundaries: +v where the effect starts, −v just after it ends. One prefix pass turns deltas back into values.
Difference array (bulk range updates)
1defapply_bookings(n:int,bookings:list[list[int]])->list[int]:2"""bookings=[[l,r,v],...](1-indexed,inclusive):addvtoseatsl..r.3O(n+b)insteadofO(n·b)."""4diff=[0]*(n+1)5forl,r,vinbookings:6diff[l-1]+=v# effect begins7diff[r]-=v# effect ends after r (0-indexed r)8out:list[int]=[]9running=010foriinrange(n):11running+=diff[i]12out.append(running)13returnout141516if__name__=="__main__":17print(apply_bookings(5,[[1,2,10],[2,3,20],[2,5,25]]))
Time: O(n + updates) vs O(n · updates) naiveSpace: O(n)
Edge cases
diff needs n + 1 slots so r at the last index doesn't overflow.
Reads BETWEEN updates force materialisation each time — the trick assumes updates batch before reads.
1-indexed problem statements: convert once at the boundary, carefully.
Common mistakes
Writing −v at r instead of r + 1 (in the problem's indexing), ending the effect one cell early.
Looping the actual range per update — the O(n·b) this exists to delete.
Complexity analysis
Operation
Best
Average
Worst
Space
Build prefix table
O(n)
O(n)
O(n)
O(n)
Range-sum query
O(1)
O(1)
O(1)
—
Subarray-sum-k count
O(n)
O(n)
O(n)
O(n)
b range updates (difference array)
O(n + b)
O(n + b)
O(n + b)
O(n)
Naive per-query re-sum
O(n) each
O(n) each
O(n·q) total
O(1)
The trade in one line: O(n) once instead of O(n) per query. If updates and queries INTERLEAVE, graduate to Fenwick/segment trees.
Python implementation
Production-quality code with type hints, validation, and docstrings.
2-D prefix sums: O(1) submatrix totals
1classMatrix2D:2"""Immutablesubmatrix-sumqueriesviainclusion-exclusion.3BuildO(R·C);queryO(1)."""45def__init__(self,grid:list[list[int]])->None:6rows,cols=len(grid),len(grid[0])ifgridelse07# P[r][c] = sum of grid[0..r-1][0..c-1] (one-cell border of zeros)8self.P=[[0]*(cols+1)for_inrange(rows+1)]9forrinrange(rows):10forcinrange(cols):11self.P[r+1][c+1]=(12grid[r][c]13+self.P[r][c+1]# above14+self.P[r+1][c]# left15-self.P[r][c]# double-counted corner16)1718defquery(self,r1:int,c1:int,r2:int,c2:int)->int:
What interviewers expect you to know
Recognition signals
'Multiple range-sum queries on unchanging data' → prefix table.
'Count/find subarrays with sum k' (especially with negatives) → prefix + hash map.
'Apply many range increments, then read' → difference array.
'Submatrix sums' → 2-D prefix.
Boundary discipline
The leading zero (prefix[0] = 0) and inclusive-right (+1) conventions eliminate the whole off-by-one class — commit to them.
For subarray-k, seen[0] = 1 IS the leading zero, wearing hash-map clothes.
Classic follow-ups
"Now the array gets point updates between queries" — prefix tables die; Fenwick (BIT) or segment tree take over at O(log n) per op.
"Longest subarray (not count) with sum k?" — store FIRST index of each prefix instead of counts.
"Why not sliding window here?" — negatives break window monotonicity; prefix map doesn't care. Being able to articulate this is the senior move.
Common mistakes
Off-by-one at the right edge
sum(l..r) = prefix[r+1] − prefix[l]. Forgetting the +1 under pressure is THE bug of this pattern — the leading-zero convention exists to prevent it.
Missing the {0: 1} seed
Subarrays starting at index 0 match against the empty prefix. Without the seed, [1, 2] with k = 3 counts 0 instead of 1.
Recording before counting
Incrementing seen[running] before querying seen[running − k] lets a length-0 subarray match itself when k = 0.
Prefix tables on mutable data
One point update invalidates O(n) table entries. Interleaved updates+queries → Fenwick/segment tree, and saying so is part of the answer.
Difference deltas at the wrong boundary
The −v goes at r + 1 (first index NOT affected). Placing it at r ends every update one element early — visible only after the materialising pass.
Practice problems
Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.
Commonly associated with: Amazon, Google, Microsoft
O(n + m) time · O(n) space
Topic quiz
4 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.
Frequently asked questions
When do I need a Fenwick tree or segment tree instead?
The moment updates and queries interleave. Prefix tables are build-once/read-many; Fenwick gives O(log n) point-update + prefix-query; segment trees add range updates and non-invertible ops (min/max).
Does the idea extend beyond sums?
To any invertible, associative op: XOR prefixes work identically (subtraction = XOR). Max/min prefixes only answer prefix queries, not general ranges — no inverse to subtract with.