Introduction to Prefix Sum Arrays

In our last few lessons, we've explored how hash maps can solve a variety of lookup problems, from finding complements to grouping anagrams using canonical keys. These patterns are incredibly powerful when you need to check for the existence of values or group items by a shared property. Today, we'll pivot to a different, but equally fundamental, array pattern that addresses another common class of problems: those involving sums over a specific range of elements.

This lesson focuses on the learning outcome: Build a one-dimensional prefix-sum array and answer range-sum queries. This technique is a classic example of a space-time trade-off. By investing a small amount of upfront computation and extra memory, we can answer certain types of repeated queries with astonishing speed. This is a core pattern you'll see frequently in interview problems.

The Problem: Repeated Range Sum Queries

Imagine you are given a static array of numbers, say, daily sales figures for a product. A common business question might be, "What were the total sales between day 10 and day 30?" or "How about from day 50 to day 60?". If you have many such queries, what's the most efficient way to answer them?

The most straightforward, or "brute-force," approach is to simply loop through the requested range for each query and add up the numbers.

function rangeSumBruteForce(nums: number[], left: number, right: number): number {
    let sum = 0;
    for (let i = left; i <= right; i++) {
        sum += nums[i];
    }
    return sum;
}

This works, but let's consider the time complexity. If a query range has k elements, the loop runs k times. In the worst case, the range could cover the entire array, making a single query an O(N) operation, where N is the total number of elements. If you have Q queries, the total time could be up to O(N * Q). For a large array and many queries, this is inefficient because we repeatedly sum the same numbers.

The Core Idea: Pre-computation with Prefix Sums

The key to optimization is to avoid this redundant work. Instead of recalculating sums from scratch every time, we can pre-compute a helper array that stores cumulative sums. This is known as a prefix sum array.

A prefix sum array, let's call it prefix, is an array where prefix[i] stores the sum of all elements in the original array from index 0 up to and including index i.

Consider the array nums = [3, 1, 4, 1, 5, 9].
Its prefix sum array would be:

• prefix[0] = 3
• prefix[1] = 3 + 1 = 4
• prefix[2] = 3 + 1 + 4 = 8
• prefix[3] = 3 + 1 + 4 + 1 = 9
• prefix[4] = 3 + 1 + 4 + 1 + 5 = 14
• prefix[5] = 3 + 1 + 4 + 1 + 5 + 9 = 23

So, prefix = [3, 4, 8, 9, 14, 23].

Building this array is efficient; you can do it in a single pass (O(N) time) because each new prefix sum is just the previous prefix sum plus the next element from the original array: prefix[i] = prefix[i-1] + nums[i].

The following image provides a great visual summary of building a prefix sum array and using it for a query.

So, how does this help us with range queries?

Answering Queries in Constant Time

With the prefix array, any range sum can be calculated with a single subtraction. The sum of elements from index L to R (inclusive) is simply the total sum up to R minus the total sum up to L-1.

Sum(L, R) = prefix[R] - prefix[L-1]

Let's use our example nums = [3, 1, 4, 1, 5, 9] and its prefix array [3, 4, 8, 9, 14, 23].
To find the sum of the range [2, 4] (i.e., 4 + 1 + 5):
Sum(2, 4) = prefix[4] - prefix[2-1] = prefix[4] - prefix[1] = 14 - 4 = 10.
And indeed, 4 + 1 + 5 = 10. It works!

This calculation takes the same amount of time regardless of how large the range is. It's an O(1) operation.

The following video provides an excellent walkthrough of this entire thought process, from the initial problem to the final, optimized solution.

A Cleaner Implementation: The N+1 Array

The formula prefix[R] - prefix[L-1] has an annoying edge case: what happens if L=0? We would try to access prefix[-1], which is an out-of-bounds error. You could handle this with an if statement, but a more elegant and common convention is to make the prefix sum array one element larger than the original array and set its first element to 0.

This N+1 sized array represents the sum of prefixes of certain lengths.

• prefix[0] = 0 (the sum of a prefix of length 0)
• prefix[1] = nums[0] (the sum of a prefix of length 1)
• prefix[i] = sum of nums[0...i-1]

With this setup, the formula for the sum of nums[L...R] (inclusive) becomes:

Sum(L, R) = prefix[R+1] - prefix[L]

Let's see this in action with nums = [3, 1, 4, 1, 5, 9].
Our new prefix array (size 7) is [0, 3, 4, 8, 9, 14, 23].

• To find Sum(2, 4): prefix[4+1] - prefix[2] = prefix[5] - prefix[2] = 14 - 4 = 10. Correct.
• To find Sum(0, 2): prefix[2+1] - prefix[0] = prefix[3] - prefix[0] = 8 - 0 = 8. Correct (3+1+4 = 8).

The edge case at L=0 is now handled seamlessly by the prefix[0] sentinel value. This is the standard implementation you should aim for.

The resource below explains this N+1 approach and provides a clean JavaScript implementation.

The following resource provides another step-by-step walkthrough of this exact N+1 method. Seeing the same concept from a slightly different perspective can help solidify your understanding.

TypeScript Template and Complexity Analysis

Here is a complete TypeScript class for the Range Sum Query - Immutable problem (LeetCode #303), using the robust N+1 pattern.

class NumArray {
    private prefix: number[];

    constructor(nums: number[]) {
        // Initialize a prefix sum array of size n+1 with a leading 0.
        this.prefix = new Array(nums.length + 1).fill(0);

        // Build the prefix sums.
        // prefix[i+1] will store the sum of nums[0...i].
        for (let i = 0; i < nums.length; i++) {
            this.prefix[i + 1] = this.prefix[i] + nums[i];
        }
    }

    sumRange(left: number, right: number): number {
        // The sum of the range nums[left...right] is the difference
        // between the sum up to 'right' and the sum up to 'left-1'.
        return this.prefix[right + 1] - this.prefix[left];
    }
}

Let's summarize the complexity:

• Time Complexity:
  • Constructor (Preprocessing): O(N) to build the prefix sum array.
  • sumRange (Query): O(1) for each query.
  • Total for Q queries: O(N + Q). This is a huge improvement over the brute-force O(N * Q).
• Space Complexity: O(N) to store the prefix sum array.

This pattern is a perfect example of a space-time trade-off. We use extra O(N) space to make our queries incredibly fast. This is only worthwhile if the array is immutable (doesn't change) and we expect to perform multiple queries.

Conclusion

In this lesson, we've added a fundamental pattern to our toolkit. The prefix sum technique allows us to answer range sum queries in constant time after a linear-time pre-computation.

Key Takeaways:

• The Problem: Answering multiple sum queries on a fixed array is inefficient if you recalculate the sum each time.
• The Solution: Pre-compute a prefix sum array, where each element stores the cumulative sum from the start of the original array.
• The Query: A range sum from L to R can be found in O(1) time using a single subtraction of two prefix sums.
• The Implementation: The most robust way to implement this is with a prefix array of size N+1, with prefix[0] = 0, which elegantly handles queries starting at index 0. The formula becomes sum(L, R) = prefix[R+1] - prefix[L].

This pattern serves as a building block for more advanced problems, such as finding subarrays with a specific sum, which we may explore later.

In our next lesson, we'll look at another important array manipulation pattern: modifying an array in-place while preserving the portion that has already been processed. This involves clever use of pointers to overwrite or shift elements without using extra memory.