leetcode 307. 区域和检索 - 数组可修改 树状数组

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
示例:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:
数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

思路：向这种单点更新，区间求和，可以用很多方法来做，分块，线段树，树状数组。
既然分到树状数组，那么就用它来做。

class NumArray {
    int[] v; //存每个点的节点 因为不是纯粹的单点加减法 所以我们还是需要知道更新前的值
    int[] sum; //记录和
    public int lowbit(int x){ 
        return x&(-x);
    }
    public NumArray(int[] nums) {
        v=new int[nums.length+1];
        sum=new int[nums.length+1];
        for(int i=0;i<nums.length;++i){
            v[i+1]=nums[i];
            init(i+1,nums[i]); //更新
        }
    }
    public void init(int i, int val) {
        int N=sum.length-1;
        while (i<=N){
            sum[i]+=val;
            i+=lowbit(i);
        }
    }
    public void update(int i, int val){
        int t=val-v[i+1]; //取值大小 转化成单增或者单减
        v[i+1]=val; //将原来的值更替为最新值
        if(t==0){ //为0不需要进行任何操作
            return;
        }
        init(i+1,t); //更新
    }
    public int sumRange(int i, int j) { //sum(j)-sum(i-1) 这里坐标需要更改 因为树状数组是从1开始的
        return sum(j+1)-sum(i);
    }
    public int sum(int i){
        int res=0;
        while (i>0){
            res+=sum[i];
            i-=lowbit(i);
        }
        return res;
    }
}