Given an integer array, write a function which returns the sum of values between two indexes.

Example:

Input: nums = [3, -7, 6, 0, -2, 5],
       [sum_range(0, 3), sum_range(2, 4), sum_range(2, 2)]
Output: [2, 4, 6]

Constraints:

• nums contains at least one element.

• Each sum_range operation will query a valid range of the input array.

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

We need to code a function sum_range(i, j), where i and j are the indexes defining the boundaries of the range to be summed up.

A naive solution is to iteratively sum the array values from index i to j, which takes linear time for each call to sum_range. Since we have access to the input array before any calls to sum_range are made, we should consider if any preprocessing can be done to improve the efficiency of sum_range.

This problem deals with subarray sums, so it might be useful to think about how prefix sums can be applied to solve it. Consider the integer array below and its prefix sums:

We already notice that the prefix sum array has some use: the prefix sum up to any index j essentially gives the answer to sum_range(0, j). For example, the sum of the range [0, 3] is just the prefix sum up to index 3:

Therefore, when i == 0:

sum_range(0, j) = prefix_sum[j]

What about when the requested range doesn’t start at 0? Let's say we want to find the sum in the range [2, 4]:

Is there a way to get this using only prefix sums? All prefix sum values are sums for ranges that start at index 0. So, let’s see how we could make use of these ranges. Consider the sum of the range [0, 4], which corresponds to prefix_sum[4]:

The key observation here is that the sum of the range [2, 4] can be obtained by subtracting the sum of the range [0, 1] from the sum above. This can be visualized:

Since the sums of ranges [0, 4] and [0, 1] are both values in our prefix sum array, we can obtain the sum of the range [2, 4] from the following expression: prefix_sum[4] - prefix_sum[1].

Therefore, when i > 0:

sum_range(i, j) = prefix_sum[j] - prefix_sum[i - 1]

Implementation

from typing import List
    
class SumBetweenRange:
    def __init__(self, nums: List[int]):
        self.prefix_sum = [nums[0]]
        for i in range(1, len(nums)):
            self.prefix_sum.append(self.prefix_sum[-1] + nums[i])
    
    def sum_range(self, i: int, j: int) -> int:
        if i == 0:
            return self.prefix_sum[j]
        return self.prefix_sum[j] - self.prefix_sum[i - 1]

struct SumBetweenRange {
    vector<long long> prefix_sum;
    SumBetweenRange(vector<int>& nums) {
        prefix_sum.assign(nums.size() + 1, 0);
        for (size_t i = 0; i < nums.size(); i++) {
            prefix_sum[i + 1] = prefix_sum[i] + nums[i];
        }
    }
    long long sumRange(int i, int j) {
        return prefix_sum[j + 1] - prefix_sum[i];
    }
};

class SumBetweenRange {
    long[] prefixSum;
    SumBetweenRange(int[] nums) {
        prefixSum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++)
            prefixSum[i + 1] = prefixSum[i] + nums[i];
    }
    long sumRange(int i, int j) { return prefixSum[j + 1] - prefixSum[i]; }
}

Complexity Analysis

Time complexity: The time complexity of the constructor is $O(n)$, where $n$ denotes the length of the array. This is because we populate a prefix_sum array of length $n$. The time complexity of sum_range is $O(1)$.

Space complexity: The space complexity is $O(n)$ due to the space taken up by the prefix_sum array.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language