Leetcode 303 Range Sum Query

题意：查询一个数组在(i,j]范围内的元素的和。

思路非常简单，做个预处理，打个表就好

拓展：可以使用树状数组来完成该统计，算法复杂度为（logn）,该数据结构强力的地方是实现简单，而且能完成实时更新以及上面的统计和

class NumArray {
public:
    vector<int> sum;
    NumArray(vector<int> &nums) {
        sum.push_back(0);
        for(vector<int>::size_type i = 0; i< nums.size(); ++i){
            int m = sum[i] + nums[i];
            sum.push_back(m);
        }
    }

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