Range Sum Query - Immutable

Problem Statement

In this task, you are required to manage a series of range sum queries on an array of integers. The primary operations involve:

1. Initializing an array with the NumArray class which takes a list of integers (nums).
2. Using the function sumRange(int left, int right) to calculate and return the sum of numbers between the left index and the right index (inclusive), both of which you specify.

The challenge aims to efficiently handle potentially numerous such sum queries, which could vary as specified in the queries.

Examples

Example 1

Input:

["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output:

[null, 1, -1, -3]

Explanation:

NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Constraints

• 1 <= nums.length <= 10⁴
• -10⁵ <= nums[i] <= 10⁵
• 0 <= left <= right < nums.length
• At most 10⁴ calls will be made to sumRange.

Approach and Intuition

Given that the problem involves range sum queries that need to be answered multiple times, an efficient solution can dramatically speed up the query response time compared to a naive approach. Here's an intuitive approach based on preprocess optimization:

1. Using Cumulative Sum (Prefix Sum): Compute the cumulative sums of the array such that each element at index i in this new array (prefixSum[i]) represents the sum of all elements from the start up to the element at index i in the original array.

   • To get the sum of elements from index left to right, calculate it as prefixSum[right] - prefixSum[left - 1]. If left is 0, then return prefixSum[right] directly.

2. Implementation Steps:

   • When initiating NumArray, compute the prefix sum array. This is an O(n) operation.
   • Each call to sumRange(left, right) becomes an O(1) operation using the prefix sum array.

This approach is optimal because:

• Query time is constant.
• Setup time is linear.
• Memory overhead is low and manageable.

This makes it well-suited for scenarios with many read-only queries and little to no updates.

Solutions

private int[] cumulativeSum;
    
public NumArray(int[] nums) {
    cumulativeSum = new int[nums.length + 1];
    for (int index = 0; index < nums.length; index++) {
        cumulativeSum[index + 1] = cumulativeSum[index] + nums[index];
    }
}
    
public int sumRange(int i, int j) {
    return cumulativeSum[j + 1] - cumulativeSum[i];
}