Prefix Sums for Efficient Range Queries

The Challenge of Repeated Range Sums

Imagine you are given a large array and need to answer thousands of queries, each asking for the sum of elements in a different sub-range. For example, in your work with financial data, you might be asked for the total return of a strategy between day 10 and day 50, then between day 20 and day 80, and so on.

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

• Time Complexity of Naive Approach: For a single query on a range of length k, this takes O(k) time. In the worst case, the range can span the entire array, making it O(n). If you have Q queries, the total time complexity becomes O(Q * n), which is too slow for many applications.

This video introduces this exact problem, highlighting the inefficiency of the naive approach.

The Prefix Sum Solution: Pre-computation for O(1) Queries

The key insight to optimize this is that the sum of a range can be calculated from the cumulative sums from the start of thearray. This is the essence of the prefix sum technique.

We create a new array, let's call it prefix, where prefix[i] stores the sum of all elements in the original array arr from index 0 up to i-1.

The process involves two main steps:

1. Pre-computation: Build the prefix array. This takes O(n) time as you only need to iterate through the original array once.
2. Querying: Use the prefix array to answer any range sum query sum(l, r) in O(1) time.

This diagram provides a perfect high-level overview of the entire technique.

The formula to get the sum of elements from index l to r (inclusive) is:

This works because prefix[r+1] contains the sum from arr[0] to arr[r], and prefix[l] contains the sum from arr[0] to arr[l-1]. Subtracting the two leaves exactly the sum from arr[l] to arr[r].

For a deeper dive into this core logic, the following reading provides an excellent, detailed explanation.

Implementation and Edge Cases

A common and elegant way to implement the prefix sum array is to make its size n+1 and initialize prefix[0] = 0. This small trick handles the edge case where the range starts at index 0 (l=0) without needing a separate if condition, as prefix[l] becomes prefix[0], which is 0.

Here is a Python implementation within a class, as is common in interview platforms like LeetCode.

from itertools import accumulate
from typing import List

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



        # The prefix sum array is of size n+1.
        # prefix_sums[i] stores the sum of the first i elements of nums.
        # initial=0 ensures prefix_sums[0] is 0.
        self.prefix_sums = list(accumulate(nums, initial=0))

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



        # The sum of elements from index left to right (inclusive) is
        # the sum up to 'right' minus the sum up to 'left-1'.
        # In our 1-based prefix_sums array, this translates to:
        # prefix_sums[right + 1] - prefix_sums[left]
        return self.prefix_sums[right + 1] - self.prefix_sums[left]




# Example Usage:
nums = [-2, 0, 3, -5, 2, -1]
num_array = NumArray(nums)
print(num_array.sumRange(0, 2))  # Output: 1  (-2 + 0 + 3)
print(num_array.sumRange(2, 5))  # Output: -1 (3 + -5 + 2 + -1)
print(num_array.sumRange(0, 5))  # Output: -3 (Sum of all elements)

Notice the use of itertools.accumulate. Given your proficiency in Python, you'll appreciate that this is a clean and efficient way to generate cumulative sums.

The following video walks through the implementation and clearly explains the initial=0 trick.

Advanced Application: Subarray Sum Equals K

The prefix sum technique is not limited to simple range sum queries. It's a powerful building block for more complex problems. A classic example is LeetCode 560: "Subarray Sum Equals K," which asks for the count of all contiguous subarrays that sum to a target value k.

Here, we can combine prefix sums with a hash map (which you'll recall from an earlier lesson). The logic is as follows:

1. Iterate through the array, calculating the current_prefix_sum.
2. For a subarray ending at index i to sum to k, we need current_prefix_sum - previous_prefix_sum = k.
3. This means we are looking for a previous_prefix_sum such that previous_prefix_sum = current_prefix_sum - k.
4. We can use a hash map to keep track of the frequencies of all prefix sums we have encountered so far. At each step, we check if current_prefix_sum - k exists in our map. If it does, we add its stored frequency to our total count.

This image provides an excellent step-by-step walkthrough of this exact algorithm.

This combination of prefix sums and hash maps is a common and powerful pattern for solving a wide range of subarray problems that go beyond simple summation.

Conclusion

In this lesson, we've explored the prefix sum technique, a fundamental tool for efficiently handling array-based queries. By investing O(n) time for pre-computation, you gain the ability to answer any range sum query in O(1) time. This time-space tradeoff is a recurring theme in algorithm design.

Key Takeaways:

• Core Idea: Pre-compute cumulative sums to answer range sum queries in constant time.
• Implementation: An O(n) pass to create a prefix array. The formula sum(l, r) = prefix[r+1] - prefix[l] then runs in O(1). Using a prefix array of size n+1 with an initial 0 elegantly handles edge cases.
• Complexity: The pre-computation is O(n) time and O(n) space. Each subsequent query is O(1) time. This is highly efficient when the number of queries is large.
• Applications: The technique is a building block for more complex problems, such as counting subarrays with a specific sum when combined with a hash map.

This lesson concludes our first module on foundational data structures and array/string patterns. You have now refreshed your understanding of complexity, lists, strings, hash maps, sliding windows, and prefix sums.

In our next module, we will shift our focus to Core Algorithms, starting with one of the most important and frequently tested algorithms: binary search.