Prefix Sum / Prefix XOR
Store cumulative totals so any range reduces to a difference of two prefixes, then use a map to count how often a required prefix appeared.
Prefix SumO(n) build, O(1) per queryNew16 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
subarray sum equals k
range sum query
count subarrays with property
The template
Get this into muscle memory, then adapt the condition per problem.
const count = new Map([[0, 1]]);
let pre = 0, ans = 0;
for (const x of nums) {
pre += x;
ans += count.get(pre - k) ?? 0;
count.set(pre, (count.get(pre) ?? 0) + 1);
} Watch Prefix Sum & Subarray CountIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Sum of a range is the difference of two running totals.
- 2You need to know how many earlier prefixes had a particular value.
- 3Seed the map with prefix zero seen once, for subarrays starting at index 0.
Drill it
Every problem in the bank that uses this pattern.
0 / 16 solved