Topic 54 of 78
Prefix Sum Pattern
Overview
The Prefix Sum pattern is a preprocessing technique that allows you to calculate the sum of any subarray in O(1) instant time. You create a new array where the value at index `i` is the total sum of all elements from `0` to `i`. Once this prefix array is built, querying the sum between any two indices `L` and `R` is a simple subtraction: `prefix[R] - prefix[L-1]`. It is mandatory for problems involving multiple range queries.
Syntax
Preprocessing takes O(N) time and O(N) space. But now, every single range query you do takes O(1) time instead of O(N).
Building and Using a Prefix Sum Array
java
public class RangeQuery {
int[] prefix;
public RangeQuery(int[] nums) {
prefix = new int[nums.length];
prefix[0] = nums[0];
// Build the prefix sum array in O(N)
for (int i = 1; i < nums.length; i++) {
prefix[i] = prefix[i - 1] + nums[i];
}
}
// O(1) Instant Query for sum between Left and Right indices
public int sumRange(int left, int right) {
if (left == 0) return prefix[right];
// Subtract the sum of the elements BEFORE the left bound
return prefix[right] - prefix[left - 1];
}
}Common Pitfalls
- Accessing `prefix[left - 1]` when `left == 0`, causing an OutOfBoundsException. You must handle `left == 0` specifically.
- Integer Overflow! A prefix sum of an array of large integers will rapidly exceed the 32-bit `int` limit. Always use `long[]` for prefix sums in production.
Interview Tips
- If a problem asks you to repeatedly query the sum (or product) of a subarray, immediately implement a Prefix Array.
Real-World Example
Financial charting software that needs to instantly display a user's total spending or stock market gains between any two custom dates without recalculating thousands of days.
example
java
// Get total volume traded between March 1st and November 15th instantly
int volume = getSumRange(march1Index, nov15Index);