快速的，动态的区间求和问题——树状数组

树状数组是一个伪二叉树数据结构，其查询与修改的代价均为O(N\log N)，其基本用途是查询任意区间和

树状数组和线段树很像，但是相较而言树状数组的效率与代码量都优于线段树，作为代价，其能解决的问题范围不如线段树广泛

树状数组的基本思想是：对于原数组A[]，用一个数组C[]来维护原数组特定区间的和，且C[ i ]对应的区间是2^k，k是i所对应的的二进制码的末尾0的个数。利用二进制补码的特性可以迅速求出C[ i ]的管辖范围

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

如果要插入一个数，则对应的操作时所有包括插入位置的区间都要增加

void add(int i,int x){
    //在原数组i位置插入x
    while(i<=n)
        c[i]+=x,i+=low(i);
}

求区间和时候，则要将所求区间分成不同的有效管辖区间求和

int sum(int i){
    int s=0;
    while(i)s+=c[i],i-=low(i);
    return s;
}

至此便是树状数组的基本操作内容了