Prefix Sum
Visualize efficient Range Sum Queries using Prefix Sum Array.
Ready to build Prefix Sum Array.
Original Array (A)
3
01
14
22
35
4-1
56
6Prefix Sum Array (P)
0
1
2
3
4
5
6
Intuition
Calculating the sum of a range [L, R] normally takes O(N) time. If we have many queries, this is slow. By pre-calculating cumulative sums, we can answer any range sum query in O(1) time.
Concept
- Prefix Sum Array (P): P[i] stores the sum of A[0]...A[i].
- Construction: P[i] = P[i-1] + A[i]. (O(N) time)
- Range Query (L, R): Sum(L, R) = P[R] - P[L-1]. (O(1) time)
How it Works
Formula:
Sum(L, R) = Sum(0, R) - Sum(0, L-1)
Sum(L, R) = P[R] - P[L-1]
Note: If L=0, Sum(0, R) = P[R].
Step-by-Step Breakdown
Watch the visualization:
- See how P[i] accumulates the sum.
- Observe how the query uses subtraction to isolate the range sum.
When to Use
- Multiple range sum queries on a static array.
- Finding subarrays with sum K.
- 2D Prefix Sums for submatrix queries.
When NOT to Use
- If the array updates frequently (updating P takes O(N)). Use Fenwick Tree or Segment Tree instead.
How to Identify
"Range Sum", "Cumulative Sum", "Subarray Sum equals K".
Frequently Asked Questions
What is Prefix Sum?
Visualize efficient Range Sum Queries using Prefix Sum Array.
What is the time complexity of Prefix Sum?
The time complexity is: Best case varies, Average case O(1), Worst case varies. Space complexity is varies.