Prefix Sum Pattern
Overview
The Prefix Sum pattern is a preprocessing technique used to execute lightning-fast queries on an array.
Imagine a system that repeatedly asks: 'What is the sum of elements from index 200 to index 500?' A naive approach would run a loop and add those 300 numbers together every single time (O(K) per query). If millions of queries are made, this grinds the system to a halt.
A Prefix Sum array solves this by pre-calculating the running total of the array at every index. prefix[i] stores the sum of all elements from index 0 up to index i.
Once this array is built (which takes O(N) time), you can answer ANY range query in O(1) absolute time using simple subtraction: Sum(i to j) = prefix[j] - prefix[i - 1].
Syntax
public class RangeQuery {
private int[] prefix;
// Pre-processing step: O(N) Time, O(N) Space
public RangeQuery(int[] nums) {
// We often make the prefix array size N+1 to cleanly handle edge cases
// where queries ask for a range starting at index 0.
prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
// Current prefix = previous prefix + current number
prefix[i + 1] = prefix[i] + nums[i];
}
}
// Query step: O(1) Time! Instantaneous.
public int queryRangeSum(int left, int right) {
// Because of our N+1 shift, right becomes right+1,
// and (left-1) just becomes left.
return prefix[right + 1] - prefix[left];
}
public static void main(String[] args) {
int[] data = {1, 2, 3, 4, 5};
// Prefix array becomes: [0, 1, 3, 6, 10, 15]
RangeQuery rq = new RangeQuery(data);
// Sum from index 1 to 3 (2 + 3 + 4 = 9)
System.out.println(rq.queryRangeSum(1, 3)); // 10 - 1 = 9. O(1) time!
}
}Common Pitfalls
- Index Out of Bounds at Index 0. If your prefix array is exactly the same size as your input array, querying
Sum(0 to j)requires calculatingprefix[j] - prefix[-1], which crashes Java. The standard industry fix is shifting the prefix array size to N+1 soprefix[0]is explicitly 0. - Integer Overflow on massive arrays. A Prefix Sum array continuously adds numbers together. If the input array has 100,000 large integers, their accumulated sum will easily exceed
Integer.MAX_VALUE. You must declare the prefix array aslong[]instead ofint[]in production. - Using it on heavily mutating data. Prefix Sums are brilliant for read-heavy systems. However, if the underlying data updates constantly (
arr[5] = 99), you have to recalculate the entire Prefix array from index 5 to N every time (O(N) update time). For mutable data, a Segment Tree or Fenwick Tree is required.
Interview Questions
Calculate the total sum of the array first. Then, iterate through the array maintaining a running leftSum. At any index, the rightSum is simply totalSum - leftSum - nums[i]. If leftSum == rightSum, you found the pivot in O(N) time and O(1) space.
Yes! A 2D Prefix Sum array allows you to instantly calculate the sum of any rectangular sub-grid in O(1) time. The math involves Inclusion-Exclusion: prefix[i][j] = val + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1].
Real-World Example
Financial Dashboards. If a dashboard displays thousands of daily transactions and allows the user to drag a slider to view 'Total Revenue between Date A and Date B', doing a loop to add millions of transactions every time the slider moves would freeze the UI. A Prefix Sum array calculates it instantly as they drag.
// UI Event Listener
public void onSliderDrag(int startDateIdx, int endDateIdx) {
// Fetches the exact total in 1 CPU cycle, ensuring 60FPS UI rendering
long totalRevenue = prefixRevenue[endDateIdx + 1] - prefixRevenue[startDateIdx];
ui.updateGraph(totalRevenue);
}Check Your Knowledge
Test your understanding of Prefix Sum Pattern with these quick questions.