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:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

Dynamic programming. Sumleft

class NumArray {
public:
    vector<long> leftSum;
    NumArray(vector<int> &nums) {
        leftSum = vector<long>(nums.size(), 0);
        if(nums.size() == 0) return ;
        leftSum[0] = nums[0];
        for(int i = 1; i < nums.size(); i++){
            leftSum[i] = leftSum[i - 1] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        if(i > j || i < 0 || j >= leftSum.size()) return 0;
        if(i == 0) return (int)leftSum[j];
        else return (int)(leftSum[j] - leftSum[i - 1]);
    }
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);