Prefix/Suffix Sums for Range Queries

1. The Core Idea: Prefix Sums for Range Queries

The basic idea of a prefix sum is simple: for an array arr, we create a new array, let's call it prefix, where prefix[i] stores the cumulative sum of all elements from arr[0] up to arr[i].

Building the Prefix Sum Array

You can build this array in a single linear pass, O(n) time. The formula is straightforward:
prefix[0] = arr[0]
prefix[i] = prefix[i-1] + arr[i] for i > 0

Here is a simple Java implementation:

public int[] computePrefixSum(int[] arr) {
    if (arr == null || arr.length == 0) {
        return new int[0];
    }
    int[] prefix = new int[arr.length];
    prefix[0] = arr[0];
    for (int i = 1; i < arr.length; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    return prefix;
}

Answering Range Queries in O(1)

Once you have the prefix array, how do you find the sum of elements in a range [l, r] (inclusive)?

• The sum from index 0 to r is simply prefix[r].
• The sum from index 0 to l-1 is prefix[l-1].

If you subtract the second from the first, you are left with the sum of elements from l to r.

So, the magic formula is:
sum(l, r) = prefix[r] - prefix[l-1]

You need to handle the edge case where l = 0. In that situation, the sum is just prefix[r].

To see this concept explained with a walkthrough, the following video is an excellent starting point.

2. The Suffix Sum and a Classic Problem: Equilibrium Index

Just as prefix sums accumulate from the start, suffix sums accumulate from the end. A suffix array would store at suffix[i] the sum of all elements from arr[i] to arr[n-1].

• Formula: suffix[n-1] = arr[n-1], and suffix[i] = suffix[i+1] + arr[i] for i < n-1.

This concept is useful in problems where you need information about the part of the array to the right of an element. A great example is the Equilibrium Index problem.

Problem: Find an index i in an array such that the sum of elements at lower indices is equal to the sum of elements at higher indices.

For an index i, we need to check if sum(0, i-1) == sum(i+1, n-1).

A naive solution would be to iterate through each index i and, for each one, calculate the left and right sums in two separate loops. This would be O(n^2). We can do much better!

An O(n) Solution:
The key is to avoid recalculating the sums. We can do this in one pass.

1. First, calculate the totalSum of the entire array.
2. Initialize a leftSum variable to 0.
3. Iterate through the array from i = 0 to n-1:
   a. Calculate the rightSum for the current index i. This is simply totalSum - leftSum - arr[i].
   b. Check if leftSum == rightSum. If they are equal, you've found an equilibrium index.
   c. Update leftSum by adding the current element: leftSum += arr[i].

Notice how leftSum is effectively a running prefix sum as we iterate. This clever trick avoids pre-calculating two separate prefix and suffix arrays.

3. Advanced Application: Subarray Sum Equals K

This is a very common interview question (LeetCode 560) that beautifully demonstrates the power of combining prefix sums with a HashMap.

Problem: Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals k.

The brute-force O(n^2) approach involves checking every possible subarray. The O(n) solution is much more elegant.

We know sum(i, j) = prefix[j] - prefix[i-1]. We are looking for cases where this equals k.
prefix[j] - prefix[i-1] = k

Rearranging this equation gives:
prefix[i-1] = prefix[j] - k

This is the crucial insight. As we iterate through the array and calculate the prefix sum up to the current index j (let's call it currentSum), we can ask: "How many times have we previously seen a prefix sum that equals currentSum - k?" Each time we have, it corresponds to a new subarray ending at j with a sum of k.

We can use a HashMap to store the frequencies of the prefix sums we've encountered so far.

The Algorithm:

1. Initialize count = 0, currentSum = 0.
2. Initialize a HashMap<Integer, Integer> called prefixSumFrequencies.
3. Put (0, 1) into the map. This is a crucial starting point to handle subarrays that start from index 0. A prefix sum of 0 has occurred once (the "empty" prefix before the array starts).
4. Iterate through the array nums:
   a. Add the current number to currentSum.
   b. Check if prefixSumFrequencies contains the key currentSum - k. If it does, add its value (the frequency) to count.
   c. Update the frequency of currentSum in the map. map.put(currentSum, map.getOrDefault(currentSum, 0) + 1).
5. Return count.

The following video provides a fantastic walkthrough of this exact logic.

4. A Glimpse into 2D Prefix Sums

The prefix sum concept can be extended to 2D matrices. A 2D prefix sum matrix, prefix[i][j], stores the sum of all elements in the rectangle from (0, 0) to (i, j). This allows you to find the sum of any submatrix in O(1) time after an O(m*n) preprocessing step. This is a very common technique in competitive programming involving grid problems.

For further study, I recommend reviewing the section on 2D prefix sums in the video (LINK, from 05:29 to 13:09) and the corresponding Java code in the article "Mastering Prefix Sum in Java" (LINK, section 3).

Conclusion

You've now learned a versatile and powerful technique for solving a wide range of array problems. By investing a linear amount of time upfront to preprocess the array, you can answer subsequent queries in constant time.

Key Takeaways:

• Prefix Sum: A technique to pre-calculate cumulative sums, allowing O(1) time for range sum queries after an O(n) setup.
• Core Formula: The sum of a range [l, r] is prefix[r] - prefix[l-1].
• HashMap Synergy: Combining prefix sums with a HashMap is a powerful pattern for solving subarray problems like "Subarray Sum Equals K" in O(n) time.
• Versatility: The core idea can be adapted to suffix sums, products, and even 2D matrices.

Preview of the next lesson:
While prefix sums can help find the sum of any subarray, what if you only want to find the subarray with the maximum possible sum? A prefix sum approach to this would still be O(n^2). In our next lesson, we will explore Kadane's Algorithm, a brilliant and elegant dynamic programming approach that solves the "Maximum Subarray Sum" problem in just O(n) time.