树状数组原理与代码

各种图示，懒得找，请百度一下
理解是，为什么会到 O(logn)
c[i]对于a[i]的管理是按照二进制位的
对于某个i，把它转为二进制

设最后有k个连续的0
当k=0时，表示i的二进制表示以1结尾，那么i就是奇数，那么c[i]=a[i]，例如c[1]=a[1], c[3]=a[3]
当k=1时，表示i的二进制表示以10结尾，那么i%2==0，i%4==2，那么c[i]=a[i-1]+a[i]，例如c[2]=a[1]+a[2], c[6]=a[5]+a[6]
当k=2时，表示i的二进制表示以100结尾，那么i%4==0，i%8==4，那么c[i]=a[i-3]+a[i-2]+a[i-1]+a[i]=c[i-2]+c[i-1]+a[i]，例如c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4]
所以，有k个连续的0，意味着管理的数是指数级增加的，为2^k个
管得最宽的i，是以2的次幂往上增长的，1，2，4，8，16，32
拿12举例，12=8+4=1100
而4=100
所以，在树状数组的图示结构里，由于它俩末尾都是2个连续的0，在管理的数的数量上是一样多的，都是4个
列个模板代码

int lowbit(int i){
    return (-i) & i;
}

int sum(int i){
    int s = 0;
    for(;i > 0; i -= lowbit(i))
        s += c[i];
    return s;
}

int sum(int i, int j){
    return sum(j) - sum(i-1);
}

注意，树状数组的下标从 1 开始，不可以从 0 开始，lowbit(0) = 0 时会出现死循环

int sum(int x, int y){
    int s = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        for(int j = y; j > 0; j -= lowbit(j))
            s += c[i][j];
    return s;
}

void add(int x, int y, int z){
    for(int i = x; i <= n; i += lowbit(i))
        for(int j = y; j <= n; j+= lowbit(j))
            c[i][j] += z;
}

int sum(int x1, int y1, int x2, int y2){
    return sum[x2][y2] + sum[x1][y1] - sum[x1-1][y2] - sum[x2][y1-1];
}

当问题满足减法规则时，可以用
Q1：区间和A[i--j]: Sum[j] - Sum[i-1]
Q2：区间最大值M[i--j]：则不能用树状数组，要么ST表，要么线段树