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...
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.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...
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.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.