【leetcode】307. Range Sum Query - Mutable

题目：
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

---

思路：
抄作业，看的博文https://www.cnblogs.com/grandyang/p/4985506.html，并借用一下ta的图。
我学习的思路是树状数组，结构如下图：

解释一下上图：数组A为原数组；数组C为数组A的前n项和，到底是前几项和？得算一下子。当i为奇数时，C[i]=A[i]；当i为偶数时，C[i]的值是，从A[i]开始向前算，前i&-i项和（好像前者也是后者的一种特殊情况）。图中各个线的意义如下（这是我手算的，数组C和数组A都是从1开始算，0号元素不管它）：
C[1]=A[1]
C[2]=A[1]+A[2]=C[1]+A[2]
C[3]=A[3]
C[4]=A[1]+A[2]+A[3]+A[4]=C[2]+C[3]+A[4]=C[2]+C[3]+A[4]
C[5]=A[5]
C[6]=A[5]+A[6]=C[5]+A[6]
C[7]=A[7]
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]=C[4]+C[6]+C[7]+A[8]
C[9]=A[9]
C[10]=A[9]+A[10]=C[9]+A[10]
C[11]=A[11]
C[12]=A[9]+A[10]+A[11]+A[12]=C[10]+C[11]+A[12]
C[13]=A[13]
C[14]=A[13]+A[14]=C[13]+A[14]
C[15]=A[15]
C[16]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]+A[9]+A[10]+A[11]+A[12]+A[13]+A[14]+A[15]+A[16]=C[8]+C[12]+C[14]+C[15]+A[16]
C[17]=A[17]
C[18]=A[17]+A[18]=C[17]+A[18]
C[19]=A[19]
C[20]=A[16]+A[17]+A[18]+A[19]+A[20]=C[16]+C[18]+C[19]+A[20]
C[21]=A[21]
C[22]=A[21]+A[22]=C[21]+A[22]
C[23]=A[23]
C[24]=A[17]+A[18]+A[19]+A[20]+A[21]+A[22]+A[23]+A[24]=C[16]+C[20]+C[22]+C[23]+A[24]
C[25]=A[25]
C[26]=A[25]+A[26]=C[25]+A[26]
……
以此类推。

---

代码实现：
代码中，数组_nums和数组sums下标也都是从1开始算，而不是0。

class NumArray {
public:
    vector<int> _nums;
    vector<int> sums;
    
    NumArray(vector<int>& nums) {
        _nums.resize(nums.size()+1);
        sums.resize(nums.size()+1);
        
        for (int i = 0; i < nums.size(); ++i){
            update(i, nums[i]);
        }
    }
    
    void update(int i, int val) {
        int diff = val - _nums[i+1];
        for (int j = i+1; j < sums.size(); j += (j&-j)){ // 正着找
            sums[j] += diff; // 它会遍历所有包含nums[i]元素的前n项和
        }
        _nums[i+1] = val;
    }
    
    int sumRange(int i, int j) {
        return getSum(j+1) - getSum(i);
    }
    
    int getSum(int i){ // 倒着找
        int ret = 0;
        for (int j = i; j > 0; j -= (j&-j)){
            ret += sums[j];
        }
        return ret;
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */

---

参考：
https://blog.csdn.net/dreamgchuan/article/details/51173561
https://www.cnblogs.com/grandyang/p/4985506.html