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

树状数组

什么是树状数组？？

看下图

其中A[i]是单个元素值，C[i]便是树状数组。

其实不难发现C[1]=A[1],C[2]=A[1]+A[2],C[3]=A[3]

其中1=（01）₂ ，2=（10）₂，3=（11）₂

好了，我们发现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，就知道是向右走。

你学会了吗？