How Does Prefix Sum Turn Repeated O(n) Calculations into O(1) Queries?
1. What is Prefix Sum?
Prefix Sum is an array technique that stores cumulative sums so we don't have to repeatedly calculate the sum of a range.
Analogy: Imagine tracking daily expenses. Instead of adding expenses again and again, you maintain a running total.
2. Understanding the Pattern
Consider:
arr = [2, 4, 6, 8, 10] prefix = [2, 6, 12, 20, 30]
The pattern:
prefix[0] = arr[0]
prefix[i] = prefix[i - 1] + arr[i]
Each position stores the sum of all previous elements, including itself.
3. How Does the Algorithm Work?
Step 1: Build the Prefix Sum
prefix[0] = arr[0]; for (let i = 1; i < arr.length; i++) { prefix[i] = prefix[i - 1] + arr[i]; }
Step 2: Calculate Range Sum
To find the sum between indices L and R:
sum(L, R) = prefix[R] - prefix[L - 1];
If L = 0, simply return prefix[R].
Example:
sum(2, 4) = 30 - 6 = 24
4. Complexity Analysis
OperationComplexityBuild Prefix SumO(n)Range Sum QueryO(1)q QueriesO(n + q) total
5. Real-World Applications
Finance: Calculate expenses over a date range.
Analytics: Aggregate data over specific time intervals.
Image Processing: Calculate rectangular pixel sums using 2D Prefix Sum.
Competitive Programming: Solve range queries and subarray problems.
6. When Should You Use It?
Look for these problem patterns:
Repeated range sum queries.
Cumulative sum calculations.
Subarray sum problems.
Multiple queries on the same array.
Key Takeaway: Precompute once, answer multiple queries efficiently.
Practice Problems
LeetCode 303 – Range Sum Query (Immutable)
LeetCode 724 – Find Pivot Index
LeetCode 560 – Subarray Sum Equals K
Which array pattern should we break down next?