2018/2/17 每日一学 树状数组
树状数组
什么是树状数组??
看下图
其中A[i]是单个元素值,C[i]便是树状数组。
其实不难发现C[1]=A[1],C[2]=A[1]+A[2],C[3]=A[3]
其中1=(01)2 ,2=(10)2,3=(11)2
好了,我们发现C[i]=A[i-2<<k+1]+……+A[I] (k为i二进制中最低位到最高位连续的0 个数)
那么,有什么办法可以迅速求出2<<k呢?
注意到对于某数x的二进制(????100000……)其中已知0的个数一定为k。那么这个1(也是最末尾的1)所代表的十进制数位2<<k.
好了,那么怎么求这个1的位置??
这里我们想到反码,按位取反加1,注意加一!!!那么此时必有原码中那个末尾的1所对应二进制位置的反码也是1(想想,为什么?)
那么2<<k=x&-x,就这样。我们解决了如何修改C数组。
那么树状数组是干啥的??
求区间和的!!
怎么求?
举个例子,求a[3]+……+a[6]
我们利用前缀和的思想,就是求sum[6]-sum[2],那么如何求sum[x]呢?
看代码:
int sum(int x) { int res=; while(x>) res+=c[x],x-=x&-x; return res; }
看到while(x>0) res+=c[x],x-=x&-x; 不难发现求sum是从当前点向左走。
如果我要使x+d怎么办?
看代码:
void add(int x,int d) { while(x<=n) c[x]+=d,x+=x&-x; }
看到x+=x&-x,就知道是向右走。
你学会了吗?