Binary Indexed Tree

• 它是一个数组
• 它用于“区段求和”
• 它平衡了区段和的更新和查询

class BIT {

    int[] array;

    public BIT(int len){
        array = new int[len+1];
    }

    public void update(int index, int value){
        // i 每次增加 最右边的1
        for(int i=index; i<array.length; i+= (i & -i)){
            array[i] += value;
        }
    }

    public int getSum(int index){
        int res = 0;
        for(int i = index; i>0; i -= (i & -1)){
            res += array[i];
        }
        return res;
    }
}

抽象的树，其实是用 lowbit 分层

• lowbit(x) = x & -x; //x 的二进制最低位 1 对应的值
• 对第 i 个+value 时，索引 i 每次按 lowbit(i)递增，所经过的所有 arr[i]都+value。每个 arr[i]，其实都存着从自己和之前 lowbit(i)个元素的总和。
• 求 0-i 的和时，arr[i]先取出来，于是 lowbit(i)+…+i 的和就知道了；i-lowbit(i)后，循环求得下一个区段总和，直到最左边。