Range Query Sum Immutable: Given an integer array nums, handle multiple queries of the following type:

1. 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]).

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^4
• -10^5 <= nums[i] <= 10^5
• 0 <= left <= right < nums.length
• At most 10^4 calls will be made to sumRange.

Try this Problem on your own or check similar problems:

1. Range Sum Query 2D - Immutable
2. Range Sum Query - Mutable

Solution:

class NumArray {
    private List<Integer> prefixSum = new ArrayList<>();
    public NumArray(int[] nums) {
        int currentSum = 0;
        for(int i = 0; i < nums.length; ++i){
            prefixSum.add(currentSum);
            currentSum += nums[i];
        }
        prefixSum.add(currentSum);
    }

    public int sumRange(int left, int right) {
        return prefixSum.get(right + 1) - prefixSum.get(left);
    }
}

Time/Space Complexity:

• Time Complexity: O(Q + n) where Q is the number of queries, and n is the length of input array
• Space Complexity: O(n) where n is the length of array

Explanation:

So in our solution we have query in O(1) and initialization O(n). It would be trivial during the query to loop over to the left index and right index and sum the numbers between,but that would leave us to O(n) time complexity on query which is not practical since we have high asymmetry between read and writes (in other words we read way more often than we write) so we have to optimize for querying. How do we do that? We can introduce prefixSum on class initialization, a prefix sum is basically the sum of all previous numbers for each of the indices in input array (in other words for element at index 2 the prefixSum will be the sum of first two number arr[0] and arr[1]). How does this help us calculate the sum between two indices? Well if substract prefixSum from the left index and prefixSum from right+1 what do we get? We get the sum of all numbers between those two indices.

Did you know about prefixSum already? Let me know in the comment section and as always Keep on crushing it!