Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 10

Prefix Sums for Range Queries

Recommended resources

Hello! In our last session, we mastered Kadane's algorithm, a prime example of how a clever, single-pass approach can solve a problem in linear time. We saw how tracking a current_sum and making a simple local decision—resetting the sum when it becomes negative—leads to a globally optimal solution for the maximum subarray sum.

Today, we'll explore another fundamental array technique: prefix sums. This method revolves around pre-computation to answer future questions with incredible speed. We'll start by learning how to use prefix sums to handle range-sum queries in constant time. Then, we'll see how this concept becomes a powerful building block for solving more complex interview problems, especially when combined with a hash map.

The Challenge: Range Sum Queries

Imagine you are given a static array of numbers, and you need to answer many queries, each asking for the sum of elements within a specific range, say from index i to j. This is a common scenario in data analysis and competitive programming.

Approach 1: The Brute-Force Solution

The most straightforward way to handle each query is to simply loop from the start index i to the end index j, adding up each element.

Let's say our array is [1, 2, 3, 4, 5] and we get a query for the range [1, 3]. We would iterate from index 1 to 3 and calculate 2 + 3 + 4 = 9.

This approach is simple to implement, but its efficiency depends on the number and size of the queries. If the array has N elements and we receive Q queries, and each query spans a large portion of the array, the total time complexity would be in the order of O(Q * N). For large inputs, this is too slow.

This GeeksforGeeks article formalizes this naive approach.

Range sum queries without updates - GeeksforGeeks

This article clearly defines the range sum query problem and presents the simple, brute-force solution first, which aligns with our learning path.

Start by reading the problem statement and the examples. Then, review the section titled [Naive Solution], focusing on the logic and the corresponding Java code provided.

Approach 2: The Optimal O(1) Query with Prefix Sums

The bottleneck in the brute-force method is re-calculating sums over and over. Many queries might overlap, forcing us to re-sum the same elements repeatedly. This is where pre-computation comes in. We can invest some time upfront to build a helper data structure that makes answering any future query almost instantaneous.

This helper structure is the prefix sum array.

A prefix sum array, let's call it prefix, is an array where each element prefix[i] stores the cumulative sum of the original array's elements from index 0 up to i.

The process of building this array is a simple O(n) loop:

  • prefix[0] = arr[0]
  • prefix[i] = prefix[i-1] + arr[i] for i > 0

The image below illustrates this process clearly.

This image shows the construction of a prefix sum array `pref` from an original array `arr`. Each element `pref[i]` is the sum of all elements in `arr` from index 0 to `i`.

Once we have this prefix array, how do we find the sum of a range [i, j]? We can use a simple and elegant formula. The sum of elements from i to j is the total sum from 0 to j, minus the total sum from 0 to i-1.

In terms of our prefix array, this translates to:

There's one edge case: if the range starts at index 0 (i.e., i = 0), the sum is simply prefix[j].

This diagram visualizes how to calculate the sum of a sub-array `A[2, 6]` using a pre-computed prefix sum array. The sum is found by taking the prefix sum at the end of the range (`A[6]`) and subtracting the prefix sum just before the start of the range (`A[1]`).

With this technique, we spend O(n) time to build the prefix sum array once. After that, every single range sum query takes O(1) time. This is a massive improvement if we have many queries.

Let's watch a video that explains this pre-processing and query logic.

LeetCode 303 Range Sum Query - Immutable | Prefix Sum | Beginner Friendly Explanation

This video from Code Harmony provides a clear, step-by-step explanation of the transition from the brute-force method to the prefix sum optimization for LeetCode's "Range Sum Query" problem.

First, watch the section that introduces the prefix sum concept as an optimization. Next, focus on how the formula for a range sum is derived from pre-computed sums. Finally, review the complete Java implementation, which shows how the prefix sum array is built in the constructor and used in the sumRange method.

Application: Solving "Subarray Sum Equals K"

The prefix sum concept is more than just a trick for range queries; it's a foundational pattern. Let's apply it to a more complex problem, a favorite in FAANG interviews: finding the longest subarray with a given sum K. This problem is especially tricky when the array contains negative numbers.

The core idea is based on the same principle we just learned. If the sum of a subarray from index i+1 to j is K, it must be that:

In terms of prefix sums:

\text{prefix_sum}[j] - \text{prefix_sum}[i] = K

By rearranging the equation, we get:

\text{prefix_sum}[i] = \text{prefix_sum}[j] - K

This gives us a powerful algorithm. We can iterate through the array from left to right, calculating the current prefix sum at each index j. For each prefix_sum[j], we check if we have previously seen a prefix sum equal to prefix_sum[j] - K.

How do we check this efficiently? With a HashMap!

The algorithm works as follows:

  1. Initialize a HashMap to store (prefix_sum, index) pairs. This map will track the first time we encounter a particular prefix sum.
  2. Initialize max_length = 0 and current_sum = 0.
  3. Iterate through the array with index i:
    a. Add arr[i] to current_sum.
    b. If current_sum == K, it means the subarray from 0 to i has the desired sum. Update max_length = i + 1.
    c. Calculate the remainder needed: rem = current_sum - K.
    d. Check if rem exists as a key in our HashMap. If it does, it means we previously ended a prefix at an index prev_i = map.get(rem). The subarray from prev_i + 1 to i must sum to K. We calculate its length i - prev_i and update max_length if it's larger.
    e. If current_sum is not already in the map, add it: map.put(current_sum, i). We only add it if it's not there because we want the earliest index for any given prefix sum to maximize the subarray length.

Let's walk through the optimal solution in the "takeUforward" tutorial.

Longest Subarray with sum K | [Postives and Negatives] - Tutorial

This article from Striver follows our preferred structure and provides an excellent explanation of using prefix sums with a hash map to solve this problem optimally.

Please read the Optimal Approach section. First, understand the core algorithm. Then, carefully study the Java code provided. Pay close attention to how the preSumMap is used to find rem = sum - k and why we only put a sum into the map if it's not already present.

To see this logic in action, let's watch Striver's dry run of a very similar problem: counting the number of subarrays with sum K. The underlying prefix sum and HashMap logic is identical, which will help you solidify the pattern.

Count Subarray sum Equals K | Brute - Better -Optimal

This video explains the prefix sum + hash map pattern with an excellent, detailed dry run. While the problem is to count subarrays, the core logic of finding sum - K in the map is the same.

Watch the section that explains the optimal solution's intuition, where the prefix_sum[j] - prefix_sum[i] = K relationship is established. Then, follow the detailed dry run to see how the hash map and prefix sum are updated at each step to find and count the subarrays.

Conclusion

In this lesson, we've added the powerful prefix sum technique to our toolkit. It's a fantastic example of a space-for-time tradeoff: we use O(n) extra space to pre-calculate sums, which in turn allows us to answer range queries in O(1) time.

Key Takeaways:

  • Range Sum Queries: A naive loop-based approach takes O(N) per query, while pre-calculating a prefix sum array allows for O(1) queries.
  • The Core Formula: The sum of elements in a range [i, j] can be found with prefix[j] - prefix[i-1].
  • Pattern Extension: The prefix sum concept is not just for simple queries. When combined with a HashMap, it provides an optimal O(N) solution to complex problems like "Longest/Count Subarray with Sum K". The key is to look for a previously seen prefix sum of current_sum - K.

We've just seen a practical application of HashMap to optimize a solution. In our next lesson, we'll dive deeper into HashMap and HashSet. We will explore more problems that can be solved efficiently by leveraging their properties for frequency counting and fast lookups, further building out your core data structures and algorithms arsenal for interviews.