Description Link to heading

303.range-sum-query-immutable

Solution Link to heading

We can use prefix sum array, so we can get sum without traversing.

Code Link to heading 

class NumArray {
private:
    vector<int> sum;
public:
    NumArray(vector<int> &nums) {
        sum.resize(nums.size(), 0);
        sum[0] = nums[0];
        for (int i = 1; i < nums.size(); i++)
            sum[i] = sum[i - 1] + nums[i];
    }
    int sumRange(int left, int right) {
        if (left == 0)
            return sum[right];
        return sum[right] - sum[left - 1];
    }
};