Prefix Sum for O(1) Range Queries

Welcome to your first lesson in the "Core Array and Subarray Techniques" module. We'll begin our journey by exploring a fundamental pattern that is surprisingly powerful: the Prefix Sum. While you may have encountered this concept in your LeetCode practice, our goal here is to ensure you have a "neat" and thorough understanding, focusing on its construction, application, and the subtle details that lead to clean, efficient code.

This lesson directly addresses the learning outcome: Construct a prefix sum array to answer range sum queries in O(1) time. We will see how a simple precomputation step can dramatically improve the efficiency of solving a common class of problems, a trade-off between space and time that is a recurring theme in algorithm design.

The Problem: Answering Many Range Sum Queries

Imagine you are analyzing daily stock returns for a portfolio. You have an array of numbers representing the profit or loss for each day. A common task is to calculate the total return over various periods, for example, "What was the total return from day 10 to day 30?" or "from day 5 to day 50?".

If you have an array of N days and you receive Q such queries, the most straightforward approach is to loop through the array for each query and add up the numbers in the given range.

• A single query for a range of length k takes O(k) time.
• In the worst case, the range could span the entire array, so a query takes O(N) time.
• Answering Q queries would then take O(N * Q) time in total.

For the constraints often seen in coding interviews (e.g., N and Q up to 100,000), an O(N * Q) solution is far too slow. This is where precomputation comes in.

To get a better feel for this problem, the following video uses an intuitive example of YouTube video performance to illustrate the inefficiency of the naive approach.

The Solution: The Prefix Sum Array

The key insight is that we can pre-calculate the cumulative sums of the array. We can create a new array, let's call it prefix_sum, where prefix_sum[i] stores the sum of all elements in the original array from the start (index 0) up to and including index i.

Let's say our original array is nums = [2, -1, 4, 5, -3].

The prefix_sum array would be constructed as follows:

• prefix_sum[0] = nums[0] = 2
• prefix_sum[1] = nums[0] + nums[1] = 2 + (-1) = 1
• prefix_sum[2] = nums[0] + nums[1] + nums[2] = 1 + 4 = 5
• prefix_sum[3] = nums[0] + ... + nums[3] = 5 + 5 = 10
• prefix_sum[4] = nums[0] + ... + nums[4] = 10 + (-3) = 7

So, prefix_sum = [2, 1, 5, 10, 7].

Notice a pattern? Each new value in the prefix sum array is just the previous prefix sum plus the current element from the original array. This gives us a simple recurrence relation for building the array:
prefix_sum[i] = prefix_sum[i-1] + nums[i] (for i > 0)

This construction process takes only one pass through the original array, giving it a time complexity of O(N).

Answering Queries in O(1)

With the prefix_sum array built, how do we find the sum of a range, say from index L to R (inclusive)?

The sum of elements from L to R is equivalent to:
(Sum of elements from 0 to R) - (Sum of elements from 0 to L-1)

Using our prefix_sum array, this translates to:
sum(L, R) = prefix_sum[R] - prefix_sum[L-1]

For our example nums = [2, -1, 4, 5, -3] and prefix_sum = [2, 1, 5, 10, 7], let's find the sum from L=1 to R=3 (i.e., [-1, 4, 5]). The true sum is 8.

Using our formula:
sum(1, 3) = prefix_sum[3] - prefix_sum[1-1] = prefix_sum[3] - prefix_sum[0] = 10 - 2 = 8.

It works! This calculation is a single subtraction, an O(1) operation.

The following reading provides a formal explanation of this technique. While it uses 1-based indexing (common in competitive programming contexts), the underlying mathematical principle is identical.

A Practical Pitfall and an Elegant Solution

The formula prefix_sum[R] - prefix_sum[L-1] has a critical edge case: what if the range starts at index L=0? The expression prefix_sum[L-1] would become prefix_sum[-1], leading to an out-of-bounds error.

You could handle this with an if statement: if L == 0, the sum is simply prefix_sum[R]. However, a more common and cleaner approach is to adjust the prefix sum array itself.

The Standard Fix: Create a prefix sum array of size N+1 and initialize it with a leading zero.

• prefix_sum[0] = 0
• prefix_sum[i+1] = prefix_sum[i] + nums[i] for i from 0 to N-1.

Let's use our example nums = [2, -1, 4, 5, -3]. The padded prefix sum array is:
prefix_sum = [0, 2, 1, 5, 10, 7]

Now, the formula for the sum of a 0-indexed range [L, R] becomes:
sum(L, R) = prefix_sum[R+1] - prefix_sum[L]

Let's re-calculate sum(1, 3):
sum(1, 3) = prefix_sum[3+1] - prefix_sum[1] = prefix_sum[4] - prefix_sum[1] = 10 - 2 = 8.

And what about the edge case, sum(0, 2)? (i.e., [2, -1, 4], which sums to 5)
sum(0, 2) = prefix_sum[2+1] - prefix_sum[0] = prefix_sum[3] - prefix_sum[0] = 5 - 0 = 5.

This padded approach handles all cases with a single, consistent formula, eliminating the need for conditional logic in your query function. This is a crucial practical detail for writing robust code under pressure.

The following video segments provide a complete walkthrough, from deriving the formula to implementing this elegant fix.

Python Implementation

Here is a clean Python implementation within a class structure, similar to what you'd see on LeetCode for a problem like "Range Sum Query - Immutable". This implementation uses the padded prefix sum array.

class NumArray:
    def __init__(self, nums: list[int]):



        # Initialize a prefix sum array of size N+1 with a leading zero.
        self.prefix_sum = [0] * (len(nums) + 1)
        



        # Build the prefix sum array.
        for i in range(len(nums)):
            self.prefix_sum[i+1] = self.prefix_sum[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:



        # Apply the universal formula.
        # This works for all valid 'left' and 'right', including left=0.
        return self.prefix_sum[right + 1] - self.prefix_sum[left]




# Example usage:
nums = [2, -1, 4, 5, -3]
numArray = NumArray(nums)
print(numArray.sumRange(1, 3))  # Output: 8
print(numArray.sumRange(0, 4))  # Output: 7

As a final note, Python's standard library offers a convenient function in the itertools module called accumulate, which can build a prefix sum array for you. list(itertools.accumulate(nums)) will produce the non-padded version.

Conclusion

In this lesson, we established a core pattern for efficiently handling range sum queries. You have learned not just the "what" but also the "why" and "how," including a key implementation detail that avoids common errors.

Key Takeaways:

• The Problem: Answering multiple range sum queries naively is inefficient (O(N*Q)).
• The Solution: Precompute a prefix sum array in O(N) time. This allows each subsequent range query to be answered in O(1) time.
• The Trade-off: We use O(N) extra space to reduce the total time complexity to O(N + Q).
• The Formula: For a 0-indexed range [L, R], the sum is prefix_sum[R] - prefix_sum[L-1].
• The Elegant Implementation: By using a padded prefix sum array (size N+1 with a leading zero), the formula simplifies to prefix_sum[R+1] - prefix_sum[L] and gracefully handles all edge cases.

This concept of precomputation is a cornerstone of algorithm design. In our next lesson, we will see how prefix sums become even more powerful when combined with another fundamental data structure: the hash map. This combination unlocks solutions to a whole new class of "subarray sum" problems that are very common in interviews.