Pattern #07
Prefix Sum
EssentialPrecompute running sums so any range sum is O(1); pair with maps for subarray sum counts.
When to use
Many range-sum queries, or count/find subarrays whose sum equals a target (prefix + hashmap).
Recognition cues
- Range sum queries
- Subarray sum equals K
- Equilibrium / pivot index
- Binary subarrays with sum (0/1 arrays)
Common pitfalls
- Off-by-one between inclusive indices and pref[i+1]
- Forgetting count[0] = 1 for empty-prefix when summing to k
- Overflow in languages with fixed integers (use long in C#)
90-second recognition drill
Which pattern fits best?
- Range sum queries
- Subarray sum equals K
- Equilibrium / pivot index
Interactive
Mental model
A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.
pref = [0, ?, ?, ?, ?]
Build prefix with pref[0] = 0.
How to think about it
Build pref once so any range is one subtraction: sum(i..j) = pref[j+1] - pref[i]. For “how many subarrays sum to k”, track how often each prefix appeared: if pref - k was seen, those earlier positions form valid subarrays ending here.
Complexity baseline
Build prefix O(n); each range query O(1). Hashmap variant for count is O(n) time and space.
Template
Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.
/** Prefix sum template: O(1) range sum after O(n) build. */
export class NumArray {
private pref: number[];
constructor(nums: number[]) {
this.pref = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) this.pref[i + 1] = this.pref[i]! + nums[i]!;
}
sumRange(left: number, right: number): number {
return this.pref[right + 1]! - this.pref[left]!;
}
}
/** Prefix sum template: O(1) range sum after O(n) build. */
export class NumArray {
private pref: number[];
constructor(nums: number[]) {
this.pref = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) this.pref[i + 1] = this.pref[i]! + nums[i]!;
}
sumRange(left: number, right: number): number {
return this.pref[right + 1]! - this.pref[left]!;
}
}
- 1#303 Range Sum Query. ImmutableGuideeasy
- 2#523 Continuous Subarray SumGuidemedium
- 3#560 Subarray Sum Equals KGuidemedium
- 4#724 Find Pivot IndexGuideeasy
- 5#930 Binary Subarrays With SumGuidemedium
- 6#974 Subarray Sums Divisible by KGuidemedium