← All patternsPrefix Sum · template
Pattern · Pointers & Windows
Prefix Sum
Store running totals so the sum of any range is one subtraction: prefix[r + 1] - prefix[l].
Time O(n) build, O(1) per query · Space O(n)
Taught in Module 5: Prefix Sum
Think of it like this
A car's odometer: to know how far you drove between two towns, subtract the reading at the first town from the reading at the second.
Clues that point here
- → Many range-sum queries
- → "Sum of subarray from i to j"
- → Values don't change between queries
- → Product or count over ranges
Not this pattern when
- ✕ The array changes between queries (use a Fenwick or segment tree)
- ✕ Only one query (just loop)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
int[] prefix = new int[arr.length + 1]; // prefix[i] = sum of arr[0..i-1]
for (int i = 0; i < arr.length; i++) prefix[i + 1] = prefix[i] + arr[i];
int rangeSum(int l, int r) { // inclusive l..r
return prefix[r + 1] - prefix[l];
}Common versions
- Range sum query
- Product of array except self (prefix and suffix products)
- 2D prefix sums
- Pivot index
Practice problems with this pattern
5.1Range Sum QueriesEasymain pattern5.2Find Pivot IndexEasymain pattern5.3Product of Array Except SelfMediummain pattern5.7Range Sum Queries on a GridMediummain pattern6.7Trapping Rain WaterHardalso uses it