Introduction to Prefix Sums
Master the technique to perform range queries in constant time.
What is a Prefix Sum?
A Prefix Sum array stores the cumulative sum of elements up to each index.
P[i] = A[0] + A[1] + ... + A[i].
It transforms array data to allow for rapid range calculations.
The Motivation: Range Queries
You have an array of daily sales: [10, 20, 5, 30, ...].
Query: "What was the total sales from Day 3 to Day 10?"
Query: "What about Day 2 to Day 8?"
If you have millions of queries, loop summing is too slow.
Attempt 1: Brute Force Loop
For each query [L, R], we loop for (i = L; i <= R) sum += A[i].
Complexity: O(N) per query. Total O(Q * N). Too slow!
Visualizing Brute Force Slowness
Initializing...
Watch how we re-calculate sums repeatedly for overlapping ranges.
When to use Prefix Sum?
Pattern Recognition Triggers:
- Subarray Sums: "Find sum of subarray..."
- Range Queries: "Calculate value between indices L and R."
- Product of Range: (Use Prefix Product).
The Intuition: Subtraction
We can find the sum of [L, R] by taking the sum of everything from 0 to R and subtracting the sum of everything from 0 to L-1.
Sum(L, R) = PrefixSum[R] - PrefixSum[L-1].
This is O(1)!
Interactive Prefix Sum
Initializing...
Watch how we answer queries instantly using the precomputed array.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.