Prefix Sum Technique
Imagine you have to answer many queries asking for the sum of elements between index i and j. Doing a loop for each query would be O(n) per query. Prefix sum precomputes cumulative sums so each query becomes O(1).
Prefix sum array `prefix[i]` stores the sum of elements from index 0 to i (inclusive).
Building prefix sum
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];
}
// prefix = [3, 4, 8, 10]
Sum from L to R (inclusive)
sum(L,R) = prefix[R] - prefix[L-1] (if L>0). If L=0, it's just prefix[R].public static int rangeSum(int[] prefix, int L, int R) {
if (L == 0) return prefix[R];
return prefix[R] - prefix[L-1];
}
Applications
- Sum queries on static arrays.
- Equilibrium index (where sum left = sum right).
- Subarray sum problems.
- 2D prefix sum for matrix range sum.
Two Minute Drill
- Prefix sum precomputes cumulative sums in O(n).
- Range sum query becomes O(1).
- Prefix array length = original length.
- Formula: sum(L,R) = prefix[R] - prefix[L-1] (with L>0).
- Useful for static arrays with many queries.
Need more clarification?
Drop us an email at career@quipoinfotech.com