# **树状数组(BIT)** ## **概述** 树状数组是一个可以用来解决单点更新和区间查询的数据结构，其复杂度为log2(n)，原则上来说，能用树状数组解决的问题就能用线段树解决，能用线段树解决的不一定能用树状数组来解决，那么我们为什么还要学习树状数组呢？因为它写起来短啊！而且不容易出错QAQ。 ## **树状数组的操作** ## * ### **树状数组的构造** ### 对于一个数组A,我们需要一个辅助数组C来进行构造树状数组。树状数组的模样就是这样：  其中: ``` C[1]=A[1] C[2]=A[1]+A[2] C[3]=A[3] C[4]=A[1]+A[2]+A[3]+A[4] C[5]=A[5] C[6]=A[5]+A[6] C[7]=A[7] C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8] ``` 将下标转化为二进制可得： ``` C[1] = C[0001] = A[1]; C[2] = C[0010] = A[1]+A[2]; C[3] = C[0011] = A[3]; C[4] = C[0100] = A[1]+A[2]+A[3]+A[4]; C[5] = C[0101] = A[5]; C[6] = C[0110] = A[5]+A[6]; C[7] = C[0111] = A[7]; C[8] = C[1000] = A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]; ``` 不难发现 ``` C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i] ``` 其中k为i的二进制从最低位到最高位连续的0 的个数。这个时候我们就要用到我们的lowbit操作了。 ``` int lowbit(int x){ return x&(-x) } ``` lowbit(x)所得到的就是2^k。 这样当我们学会了lowbit操作时。我们就可以进行单点更新和区间查询了。 * ### **单点更新** 参照上图，假如我们要对A[1]进行加k操作，那么我们需要更新的C数组就该是: ``` 1 C[1]+=k 1+lowbit(1)=2 C[2]+=k 2+lowbit(2)=4 C[4]+=k 4+lowbit(4)=8 C[8]+=k end ``` 这样用代码表示即为: ``` void update(int id,int k){ for(int i=id;i<=n;i+=lowbit(i)) C[i]+=k; } ``` * ### **区间查询**