Problem Description

Question

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Input

["NumArray", "sumRange", "sumRange", "sumRange"]

[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output

[null, 1, -1, -3]

Explanation

Approaches

The simplest way to solve this problem is to calculate the sum of elements from i to j every time a query is made.

For each query, loop through the range from i to j and sum up the elements.
This approach is straightforward but not efficient for large numbers of queries or larger input sizes.

Complexity Analysis

Time Complexity: O(n) per query, where n is the number of elements in the range [i, j].
Space Complexity: O(1) for handling each query since no additional space is used other than input storage.

A more optimal approach is to preprocess the input array to create a prefix sum array.

The prefix sum at each index i stores the cumulative sum of the array from 0 to i.
For a query to get the sum from index i to j, we can use the formula: [ \text{sumRange}(i, j) = \text{prefixSum}[j] - \text{prefixSum}[i-1] ]
This reduces the time complexity of each query to O(1).

Initialize a prefix sum array with an extra zero at the start for ease of calculation.
For each element in the input array, calculate the cumulative sum and store it in the prefix sum array.
When a query is made, use the formula above to get the sum in constant time.

Complexity Analysis

Time Complexity: O(n) for preprocessing where n is the number of elements in the input array. O(1) for each sum range query.
Space Complexity: O(n) due to the prefix sum array.