仅供自己学习
思路：
这一道题可以很简单很暴力的算出来，既然求下标为j之前所有元素之和，那么第一时间就会想到是不是可以for循环这样一个一个加起来然后返回，这样是没错，但是有个问题，会超时。
题目提到会多次调用sumRange这个函数，如果每次都是O（n）的for循环 多调用几次那么时间复杂度会很高。
那么我们主要的任务就是降低sumRange这个函数的时间复杂度，如果我们能有办法存储所有J下标之前的元素的和，那么我们在sumRange函数直接调用，那么就是O（1）的时间复杂度。因此我们在NumArray这个函数中，先把J下标之前的和存储起来，用一个vector，而我们只需要一个nums.size（）大小的for循环，根据公式
sums[J+1]=sums[J]+nums[i]即可。
代码：
1 class NumArray { 2 public: 3 vector<int> sums; 4 NumArray(vector<int>& nums) { 5 sums.resize(nums.size()+1); 6 for(int i=0;i<nums.size();++i){ 7 sums[i+1]=sum[i]+nums[i]; 8 } 9 10 } 11 12 int sumRange(int i, int j) { 13 return sums[j+1]-sums[i]; 14 } 15 }; 16 17 /** 18 * Your NumArray object will be instantiated and called as such: 19 * NumArray* obj = new NumArray(nums); 20 * int param_1 = obj->sumRange(i,j); 21 */
303. Range Sum Query - Immutable
原文：https://www.cnblogs.com/Mrsdwang/p/14468191.html