树状数组

树状数组

目的：计算任意一段连续子数组的元素和小，并且修改其中某个元素的复杂度也小

把任意前缀拆分成若干个关键区间，使得更新操作也只会更新若干个关键区间

拆分

根据2的幂进行拆分

8:100

拆分成8个关键区间：[1,1],[1,2],[3,3],[1,4],[5,5],[5,6],[7,7],[1,8]

只取最右边的区间，因为每一次除了最右边的，剩下的都在之前出现过了(可以用dp思想证明)

计算

lowbit(i)：i的二进制的最后一位，如14(1110)，lowbit(13)=4(10)

由于关键区间的右端点互不相同，我们可以把右端点为 iii 的关键区间的元素和保存在 tree[i]中。

按照如下方法计算前缀 [1,i] 的元素和：

1. 初始化元素和 s=0。
2. 每次循环，把tree[i]加到s中，对应关键区间[i-lowbit(i)+1,d]的元素和。
3. 然后更新i为i-lowbit(i),表示接下来要拆分[1，i-lowbit(i)],获取其中关键区间的元素和。
4. 循环直到i=0为止。
5. 返回s

时间复杂度O(logn)

更新

e.g.：更新下标10

如图，要更新10、12、16

10:01010 + lowbit(10)

12:01100 + lowbit(12)

16:10000

只需要不停地+lowbit即可，便可以遍历到每一个需要改变的下标

对于update(index,val),算法如下： 1.设delta=val-nums[index],相当于把index的元素增加了这么多。然后把nums[index]更新成val。 2.初始化i=index+1(注意下标从1开始)，这是第一个被更新的关键区间的右端点。 3.不断循环直到i>n,这里n是nums的长度。 4.每次循环，把tree[i]增加delta。 5.然后更新i为i+lowbit(),即下一个被更新的关键区间的右端点。

如何求lowbit(i)

lowbit(i) = i & (-i) = i &= (-i)

相当于和补码进行和操作

二进制的补码，就是十进制的取负

初始化

最后剩下的问题是，如何根据nums初始化，也就是把每个关键区间的元素和tree[i]算出来。 最简单的做法是，把tree[d]初始化成0，然后对每个nums[i],调用一次update(i,ums[i])。

for(int i=0;i<nums.length;i++){
    for(int j =i+1;j<tree.length;j += j&-j){
		tree[j] += nums[i];
	}
}

也可以，直接把这些update操作合并到一起。从1开始枚举i,把nums[i-1]加到tree[i]后，tree[i]就算好了，直接把tree[i]加到下一个关键区间的元素和中，也就是加到tree[i+lowbit(i)]中。下一个关键区间的元素和由tree[i+lowbit(i)]来更新，我们只需要继续往后枚举i就行。

for(int i =1;i<tree.length;i++){
	tree[i] += nums[i-1];
	int next = i + (i&-i);
	if(next<tree.length){
		tree[next] += tree[i];
	}
}

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

class NumArray {
    private int[] nums;
    private int[] tree;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.tree = new int[nums.length+1];
        //下标从1开始
        //tree[i+1]代表以i为末尾的拆分

//        for(int i=0;i<nums.length;i++){
//            for(int j =i+1;j<tree.length;j += j&-j){
//                tree[j] += nums[i];
//            }
//        }
        for(int i =1;i<tree.length;i++){
            tree[i] += nums[i-1];
            int next = i + (i&-i);
            if(next<tree.length){
                tree[next] += tree[i];
            }
        }

    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        for(int i = index+1;i<tree.length;i += i&-i){
            tree[i] += delta;
        }
    }

    private int getSum(int n){
        int res = 0;
        for(int i = n;i>0;i -= i&-i){
            res += tree[i];
        }
        return res;
    }

    public int sumRange(int left, int right) {
        return getSum(right+1) - getSum(left);
    }
    
}