➕ Prefix Sum
One-line summary: Pre-compute cumulative sums so any range query
sum(L..R)is answered in O(1) after O(n) preprocessing.
🎯 Concept
A prefix sum (a.k.a. cumulative sum) pre-computes running totals so that the sum of any range can be answered in O(1) — no matter how large the range.
Build a prefix sum array p where p[i] = arr[0] + arr[1] + ... + arr[i-1] (1-indexed to avoid the p[-1] edge case):
Range sum [L, R] = p[R + 1] - p[L] (with p[0] = 0)
flowchart LR
A["arr = [2, 4, 1, 3]"] --> B["p[0]=0"]
B --> C["p[1]=2"]
C --> D["p[2]=6"]
D --> E["p[3]=7"]
E --> F["p[4]=10"]
F --> G["sum(1..3) = p[4]-p[1] = 10-2 = 8"]
Difference array is the inverse: apply range updates in O(1), then read final values in O(n) via a single prefix-sum pass.
1D vs 2D Prefix Sum
- 1D:
p[i+1] = p[i] + arr[i]. Answerssum(L..R)in O(1). - 2D:
p[i][j]stores the sum of the rectangle from(0,0)to(i-1,j-1). Uses inclusion–exclusion:
p[i][j] = arr[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]
rectSum(r1,c1,r2,c2) = p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]
Diagram
⚡ Time & Space Complexity
| Operation | Time | Space | Notes |
|---|---|---|---|
| Build 1D prefix array | O(n) | O(n) | One pass |
| 1D range query | O(1) | O(1) | Two lookups |
| Difference array update | O(1) | O(n) | Read values in O(n) |
| Build 2D prefix array | O(m·n) | O(m·n) | Inclusion–exclusion |
| 2D rectangle query | O(1) | O(1) | Four lookups |
Key Insight: Preprocessing pays off when you have many queries on a static array — amortize O(n) build across O(1) queries.
Common Patterns
Basic Prefix Sum
function buildPrefix(arr) {
const p = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) p[i + 1] = p[i] + arr[i];
return p;
}
function rangeSum(p, l, r) {
return p[r + 1] - p[l];
}
Subarray Sum Equals K (hash map + prefix)
function subarraySum(nums, k) {
const map = new Map([[0, 1]]);
let count = 0,
sum = 0;
for (const n of nums) {
sum += n;
count += map.get(sum - k) || 0;
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
2D Prefix Sum (Matrix Range Query)
class NumMatrix {
constructor(matrix) {
const m = matrix.length,
n = matrix[0].length;
this.p = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
this.p[i][j] =
matrix[i - 1][j - 1] + this.p[i - 1][j] + this.p[i][j - 1] - this.p[i - 1][j - 1];
}
sumRegion(r1, c1, r2, c2) {
return this.p[r2 + 1][c2 + 1] - this.p[r1][c2 + 1] - this.p[r2 + 1][c1] + this.p[r1][c1];
}
}
// Build: O(m*n), Query: O(1)
🧪 Worked Example: Pivot Index
Find the index where the sum of elements to the left equals the sum to the right.
function pivotIndex(nums) {
const total = nums.reduce((s, x) => s + x, 0);
let leftSum = 0;
for (let i = 0; i < nums.length; i++) {
// right sum = total - leftSum - nums[i]
if (leftSum === total - leftSum - nums[i]) return i;
leftSum += nums[i];
}
return -1;
}
// A running prefix (leftSum) lets us check the balance point in one pass.
// Time: O(n), Space: O(1)
Pitfalls
- Off-by-one: use 1-indexed prefix array to avoid
p[-1]issues - 2D prefix sum: remember the inclusion-exclusion formula
Practice Problems
Related Topics
- Hashing — hash map powers subarray sum = K
- Kadane's Algorithm — complementary
- Sliding Window
← Back to Home · © sparshjaswal