Prefix Sums for O(1) Range Sum Queries

The Problem: Repeated Range Sum Queries

Let's consider a common problem: you are given a static array of numbers, and you need to build a service that can quickly answer queries for the sum of elements between any two indices, left and right.

The most straightforward approach is to loop from left to right and add up the elements for each query.

// Naive approach
public int sumRange(int[] nums, int left, int right) {
    int sum = 0;
    for (int i = left; i <= right; i++) {
        sum += nums[i];
    }
    return sum;
}

If the range has $k$ elements, this takes $O(k)$ time. In the worst case, a query could span the entire array, making it an $O(n)$ operation. If you have $Q$ queries, the total time complexity would be $O(Q\cdot n)$, which is too slow for many applications.

The key to optimization lies in precomputation. Can we invest some time upfront to make all future queries faster?

The Prefix Sum Solution

The prefix sum technique does exactly this. The core idea is to create an auxiliary array, let's call it prefixSum, where each element prefixSum[i] stores the cumulative sum of the original array's elements from the beginning up to index i.

The following video provides an excellent conceptual introduction to this idea. It starts with the naive approach and builds the intuition for why precomputing cumulative sums is so powerful.

As the video explained, once you have the prefix sum array, you can find the sum of any range [left, right] with a single subtraction.

Let's formalize this. Given an original array nums, we will construct a prefixSum array. A very common and robust implementation detail is to make the prefixSum array one element larger than the original nums array. This helps simplify the calculations and avoid edge cases.

We define it as follows:

• prefixSum[0] = 0
• prefixSum[i] = nums[0] + nums[1] + ... + nums[i-1] for i > 0

In other words, prefixSum[i] is the sum of the first i elements of nums.
This array can be built in $O(n)$ time using the recurrence relation:

With this structure, the sum of elements from index left to right (inclusive) is simply:

Why does this work?

• prefixSum[right + 1] gives you the sum from nums[0] up to nums[right].
• prefixSum[left] gives you the sum from nums[0] up to nums[left - 1].

Subtracting the two cancels out the initial part of the sum, leaving exactly the sum of nums[left] through nums[right]. This entire process is captured perfectly in the following diagram.

From Theory to Java Implementation

Now, let's translate this into a practical Java class, as you might be asked to do in an interview (this is the essence of LeetCode problem 303: Range Sum Query - Immutable).

The following resource provides an in-depth explanation and a clean Java implementation. Pay close attention to how the prefixSum array is one larger than the input array and how this simplifies the sumRange calculation.

With the logic clear, let's examine the corresponding Java code.

Complexity and Common Pitfalls

For your Google interview preparation, analyzing complexity and anticipating edge cases is crucial. Let's summarize and then look at potential mistakes.

Time and Space Complexity:

• Preprocessing (Constructor): The constructor iterates through the input array once to build the prefixSum array. This takes $O(n)$ time.
• Query (sumRange): The sumRange method performs a single subtraction, regardless of the range size. This takes $O(1)$ time.
• Space Complexity: We store an additional array of size $n+1$. This requires $O(n)$ space.

The key trade-off, which you should be prepared to discuss, is using $O(n)$ extra space to reduce query time from $O(n)$ to $O(1)$. This is highly advantageous when you expect many queries on an unchanging array.

Making this technique robust means avoiding common mistakes. The most frequent are off-by-one errors in indexing.

Conclusion

In this lesson, you've learned the prefix sum technique, a powerful pattern for handling range sum queries on static arrays. It embodies a classic algorithmic trade-off: investing in preprocessing to achieve remarkable query performance.

Here are the key takeaways:

• Prefix Sum: A technique that precomputes cumulative sums to answer range queries efficiently.
• Preprocessing: Building the prefix sum array takes $O(n)$ time and uses $O(n)$ space.
• Querying: Finding the sum of any range [left, right] takes $O(1)$ time with a simple subtraction: prefixSum[right + 1] - prefixSum[left].
• Implementation: Using a prefixSum array of size n+1 with an initial 0 is a robust way to avoid edge-case handling for ranges starting at index 0.

We've just seen a technique that cleverly uses extra space to gain a significant advantage in time. In our next lesson, we'll tackle problems with the opposite constraint. We will explore in-place array manipulation, where the challenge is to modify an array using no extra space, forcing you to be creative within the array's own memory.