BIT（数状数组）

---

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;
  }
}