树状数组笔记
树状数组，就是这么简单！_哔哩哔哩_bilibili
c[]是管理数组，也是树状数组
求x的二进制表示下最低位的1及他后面的0构成的值：
lowbit(x)= x&(-x);
管理数组c[i] 的区间长度 ：lowbit(i)
c[i]的直接前驱为c[i-lowbit(i)] 即c[i]左侧紧邻的子树的根
c[i]的直接后继为c[i+lowbit(i)] 即c[i]的父节点
c[]的下标从1开始，如果为0则lowbit(0)=0，卡住
计算前缀和：sum[7]=c[7]+c[6]+c[4] sum[9]=c[9]+c[8]
对a数组更新：a[i]+k ---> c[5]+k然后c[5]的后继都加k即c[6]+k、c[8]+k
计算区间和：a[i]+a[i+1]+...+a[j] ，即sum[j]-sum[i-1]
int lowbit(int x){//c的区间长度
return x&(-x);
}void add(int i , int k){ //点更新 点i加上k
//n为数组长度
for(;i<=n;i+=lowbit(i))//累加所有后继(父节点)
c[i]+=k;
}int sum(int i){//前缀和 a[1]...a[i]
int ans=0;
for(;i>0;i-=lowbit(i)) //累加所有前驱
ans+=c[i];
return ans;
}int qjsum(int i , int j){//区间和 ，a[i]+..+a[j]
return sum(j)-sum(i-1);
}
点更新，从叶子更新到树根，不超过树高O(logn)
前缀和，从节点一直查找前驱，前驱个数不超O(logn)
局限
//https://vjudge.net/article/2642
2352 -- Stars 题解Stars_小郑的ac路的博客-CSDN博客