leetcode Question: Range Sum Query - Immutable

Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.

Analysis:

This is a simple DP problem. By just watching the example, we could easily find the solution:

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

For each index i we could compute the sum from 0 to i:

sum = [-2, -2+0, -2+0+3, -2+0+3-5, -2+0+3-5+2, -2+0+3-5+2-1]

Therefore, if we want to find the sum between i and j:

• sum[ i ] can be viewed as sum[ 0 to i ]
• sum[ j ] can be viewed as sum[ 0 to j ]
• sum[ i-1 ] + sum[ i to j ] = s[ 0 to j ]
• sum [ i to j ] = sum[ j ] - sum[ i-1 ]

Code (C++):

class NumArray {

public:

NumArray(vector<int> &nums) {

sums = nums;

for (int i = 1; i< nums.size(); i++){

sums[i] = sums[i-1] + nums[i];

}

}

int sumRange(int i, int j) {

return i==0 ? sums[j] : sums[j] - sums[i-1];

}

private:

vector<int> sums;

};

// Your NumArray object will be instantiated and called as such:

// NumArray numArray(nums);

// numArray.sumRange(0, 1);

// numArray.sumRange(1, 2);

Code (Python):

class NumArray(object):

def __init__(self, nums):

"""

initialize your data structure here.

:type nums: List[int]

"""

self.sums = nums[:]

for i in range(1, len(self.sums)):

self.sums[i] = self.sums[i-1] + nums[i]

def sumRange(self, i, j):

"""

sum of elements nums[i..j], inclusive.

:type i: int

:type j: int

:rtype: int

"""

if i == 0:

return self.sums[j]

else:

return self.sums[j] - self.sums[i-1]

# Your NumArray object will be instantiated and called as such:

# numArray = NumArray(nums)

# numArray.sumRange(0, 1)

# numArray.sumRange(1, 2)