2018/2/17 每日一学 树状数组

树状数组

什么是树状数组??

看下图

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,就知道是向右走。

你学会了吗?

相关推荐