Imagine being asked multiple times:
“What’s the sum from index L to R?”
If you loop every time, your solution becomes slow.
But what if you could answer every query in O(1)?
That’s exactly what Prefix Sum does.
What is Prefix Sum?
Prefix sum stores cumulative sums.
Each index stores sum from 0 to i
int[] arr = {3, 1, 4, 2};
int[] prefix = new int[arr.length];
prefix[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
prefix[i] = prefix[i-1] + arr[i];
}
Result:
prefix = [3, 4, 8, 10]
Why Prefix Sum is Powerful
Without prefix sum:
- Each query → O(n)
With prefix sum:
- Preprocessing → O(n)
- Each query → O(1)
Range Sum Formula
Use this:
- S(L,R)=prefix[R]−prefix[L−1]
Special case:
- If L = 0 → just prefix[R]
Implementation
public static int rangeSum(int[] prefix, int L, int R) {
if (L == 0) return prefix[R];
return prefix[R] - prefix[L-1];
}
The Real Insight
Do work once → reuse many times
Instead of solving each query separately,
you precompute smartly.
Applications
- Range sum queries
- Subarray sum problems
- Equilibrium index
- 2D prefix sum (matrix problems)
For More: https://www.quipoin.com/tutorial/data-structure-with-java/prefix-sum-technique