问题描述 链接到标题

303.区域和检索-数组不可变

解题思路 链接到标题

利用前缀和数组，使得求区间和时无需再遍历数组求和。

代码 链接到标题 

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];
    }
};