树状数组入门+代码

原理

一些形象化的理解树状数组的原理的介绍：https://www.zhihu.com/question/54404092

知乎上用户猪鼻蛇给的图比较形象些，这个lowbit可以表示当前点对应的到左右两个点的路径长度。

比如sum[6]（sum数组来表示树状数组）左边的就是sum[4]，右边就是sum[8]，而lowbit(6)正好等于2。这样其实也没有解释其具体的原理，但是形象化了理解了树状数组的过程。

这里开辟的树状数组的长度n，也就是有n个数。

树状数组用来实现 点更新、区间和查询 这两个功能。

一次求区间和的复杂度为logn，一次点更新复杂度也是logn，这个还是很好的。

注意：我们使用的数组是从1开始的，编号为0的数组节点没有用到。

代码实现

//点查询，需要更新的点 的编号为id，数组长度为n
void up(int id, int x){
    while(id < n){
        sum[id] += x;
        id += i&(-id);
    }
}

//区间和查询，注意这里其实是从1到点id之间的区间和
int getsum(int id){
	int res = 0;
    while(id>0){
        res += sum[id];
        id -= id&(-id);
    }
    return res;
}