Prefix Sum & Difference Arrays
Quick Overview
Precomputing running totals turns any range sum into one subtraction: `prefix[R+1] - prefix[L]`. Queries drop from `O(N)` each to `O(1)`, paid for once by an `O(N)` build.
Deep Dive
1. The Power of Pre-computation
Suppose you need to calculate the sum of array elements from index L to R thousands of times. A loop takes O(N) per query. A Prefix Sum Array pre-computes cumulative totals in O(N) once, answering every subsequent query in O(1) instant time!
2. Prefix Sum Formula
prefix[i] = prefix[i - 1] + arr[i - 1]
Sum(L..R) = prefix[R + 1] - prefix[L]
3. Implementation
class PrefixSum {
constructor(nums) {
this.prefix = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
this.prefix[i + 1] = this.prefix[i] + nums[i];
}
}
queryRange(left, right) {
// Returns sum of elements from index left to right inclusive in O(1)
return this.prefix[right + 1] - this.prefix[left];
}
}
const tracker = new PrefixSum([3, 1, 4, 1, 5, 9, 2]);
// Prefix array: [0, 3, 4, 8, 9, 14, 23, 25]
console.log(tracker.queryRange(1, 4)); // Elements [1, 4, 1, 5] -> Output: 11
console.log(tracker.queryRange(0, 2)); // Elements [3, 1, 4] -> Output: 8
4. Subarray Sum Equals K (Prefix Sum + Hash Map)
Find the total number of continuous subarrays whose sum equals k in O(N) time:
function subarraySum(nums, k) {
const prefixCount = new Map([[0, 1]]);
let currentSum = 0;
let totalCount = 0;
for (const num of nums) {
currentSum += num;
if (prefixCount.has(currentSum - k)) {
totalCount += prefixCount.get(currentSum - k);
}
prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
}
return totalCount;
}
console.log(subarraySum([1, 1, 1], 2)); // Output: 2
5. Common Mistakes
- Off-By-One Indexing: Using a 0-indexed prefix array of size
Nrequires messyleft === 0special casing. Allocating sizeN + 1withprefix[0] = 0eliminates boundary edge cases cleanly!
6. Next Steps
Use prefix sums for range queries and subarray sum problems. Next, let's explore Recursion and Call Stack Frames!
Next Up in Data Structures & Algorithms Core Patterns
Big O Notation: Time & Space Complexity
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
Dynamic Arrays & Amortized Resizing
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
Two Pointers Pattern (Converging & Symmetrical)
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.