树状数组模板(书上的)

树状数组模板

白书P177 紫书P196 还有我真的认为ADD()中是while(pos<=maxn) 因为你要更新 就要把所以的都更新了 不能只把你这一次求的更新了 虽然你这一次是对的 那么对于下一次询问 那么就有可能是错的了 因为你没有向上更新

PS:树状数组只支持 , ①单点更新 , ②区间查询 , 不支持区间更新哦!

&代码：

int bit[maxn],n;
void SUM(int x,int& ans){
    ans=0;
    while(x>=1){
        ans+=bit[x];
        x-= x&-x;
    }
}

void ADD(int pos,int x){
    //书上是这么说 但我觉得应该是 pos<=maxn
    while(pos<=n){
        bit[pos]+=x;
        pos+= pos&-pos;
    }
}