303. Range Sum Query - Immutable

Given an integer arraynums, find the sum of the elements between indicesiandj(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.

Solution

presum array.

class NumArray {
    vector<int> preSum;
public:
    NumArray(vector<int> nums) {
        preSum = vector<int>(nums.size() + 1, 0);
        for(int loop = 1; loop <= nums.size(); ++loop) {
            preSum[loop] = preSum[loop - 1] + nums[loop - 1];
        }
    }

    int sumRange(int i, int j) {
        return preSum[j+1] - preSum[i];
    }
};