lowbit运算
lowbit(x)=x&(-x)，从二进制的角度解读就是取(0000001101001100)2 最右边的1和它后边的所有0，即(100)2
可以理解为能整除x的最大的2^n
C数组是什么？
解释： BIT存放i自身及之前的lowbit(i)个整数之和的数组
C[8]=A[1]+A[2]+...A[8]
C[7]=A[7]
C[6]=A[5]+A[6]
C[5]=A[5]
C[4]=A[1]+A[2]+A[3]+A[4]
以C[4]为例，lowbit(4)=4，所以包含了前面4个，即A[1]->A[4]之和。
以C[5]为例，lowbit(5)=1，所以只包含了C[5]。
想求前14项的和只需要求A[14]+C[13]+C[12]+C[8]即可，即
C[c]=A[c]+C[c-1]+C[c-1-lowbit(c-1)]+C[c-1-lowbit(c-1)-lowbit(c-1-lowbit(c-1))]+...
image.png
C数组怎么求？
代码实现：
// 单个数组成员的大小
int A[N]={0};
// 前面i位的数组值之和
int C[N]={0};
int lowbit(int num){
// 不能处理0的情况,直接返回减去最右边的1后的值
return num-(num&(-num));
}
int countC(int c){
int i,j;
// 在c的时候C[c]+=A[c]
C[c]+=A[c];
//cout<<"add:"<<A[c]<<endl;
int length=c;
length--;
// 在小于c的时候,C[c]+=C[length],减少计算量.
while(length>lowbit(c)){
// 只对前面lowbit(c)个元素(含自身)求和
C[c]+=C[length];
//cout<<"add length["<<length<<"]:"<<C[length]<<endl;
length=lowbit(length);
// C[c]是由一系列 C[length-lowbit(length)]组成的(length从c-1开始起步)
}
}
怎么获取前n项的和？
sum[i]=C[i]+C[i-lowbit[i]]+C[i-lowbit[i]-lowbit(i-lowbit[i])]+...
int getSum(int num){
int length=num;
int sum=0;
while(length>0){
sum+=C[length];
length=lowbit(length);
}
return sum;
}
跟直接缓存sum[i]有什么区别？
通过将sum切割，在需要update某个值的时候就可以只修改与它相关的几个C[i]即可。
需要修改A[I]值的话怎么办？
逐+=lowbit(i)位对C[i]+=add
void update(int num,int add){
int i;
A[num]+=add;
for(i=num;i<length;i+=lowbit(i)){
C[i]+=add;
}
}
