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]`

).

**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 <= 104`

`-105 <= nums[i] <= 105`

`0 <= left <= right < nums.length`

- At most
`104`

calls will be made to`sumRange`

Approach 1 :

Naive approach here is , for each call to subrange , the for loop executes starting from the left to right index position and the sum is found out. This takes total complexity at max equal to :

Time: O(n*number of calls to subrange)

Space:O(1)

Approach 2:

This solution can be optimised to a linear time for each function call. This is achieved by using dynamic programming. This repeated work of finding sum between the index left and right, inclusive of both is overlapping problem. The idea here is to compensate between space and time. We create an additional array dp, and value at dp[i] is the sum of all terms upto i-1 terms in the nums array, Thus dp is n+1 in size, where n is size of nums. So if you want to calculate the sum of terms from left and right index position is simply dp[right+1]-dp[left].

def __init__(self, nums: List[int]):

self.nums=nums

self.dp=[]

self.dp.append(0)

for i in range(len(self.nums)):

self.dp.append(self.dp[-1]+nums[i])def sumRange(self, left: int, right: int) -> int:

return(self.dp[right+1]-self.dp[left])

Time : O(n + 1*number of call to subrange)

Space :O(n)