树状数组
今天听老刘讲了下树状数组,再结合自己的理解。补一篇学习笔记。
树状数组的用处:
1.单点修改+区间查询(本质)
2.区间修改+单点查询
3.区间修改+区间查询
当我们需要频繁的修改查询时,借用树状数组可以大大降低复杂度。(o(logn))
而且树状数组较线段树的好处就是:代码简洁。(能让你深切感受到二进制之美)
下面就来介绍一下如何构造使用树状数组。
预备知识(lowbit)
给你一个数,其转化为二进制从右往左到第1个1的值就是这个数的lowbit值。
eg:12(1100)的lowbit值即为4(100)
那么,lowbit(x)要怎么去计算呢?
首先我们把x取反+1,这样得到的(~x+1)与之前的x相比只有第一个1(从右往左)的后面的数相同了。
所以lowbit(x)=x&(~x+1)
由于计算机存储的采用是补码,所以~x+1=-x,那么lowbit(x)=x&-x
单点修改+区间查询
给出一个长度为n的数组,完成以下操作:
1.将第x个数加上k
2.输出区间[l,r]内每个数的和

如上图所示,原数组设为a,树状数组设为t。
t[1] (0001)=a[1] (0001);
t[2] (0010)=a[1] (0001)+a[2] (0010);
t[3] (0011)=a[3] (0011);
t[4] (0100)=a[1] (0001)+a[2] (0010)+a[3] (0011)+a[4] (0100);
以此类推。
以这样的方式来存储数组的数据结构其实就是树状数组了。
可以发现,t[x]管理的a[x]的数量取决于lowbit(x)
而现在我们要求sum(4),其实就是t[4]的值。
sum(6)(0110)=t[6](0110)+t[4] (0010)
sum (7)(0111)= t[7] (0111) + t[6](0110)+t[4] (0010)
又可以发现,我们要求sum(x),只要从x开始不断减去lowbit(x),就能还原整个管理区域。这样就保证了
sum(x)的复杂度最多是logx。也是为什么使用树状数组的原因。
那么当我们要进行单点更新时,不光要将t[x]+k,还要将管理x的t都加上k,也就是sum的逆向,不断加上lowbit(x)就行了。
贴下板子(非常的简洁哟):
|
|
tip:树状数组下标不能从0开始,会陷入死循环)
区间修改+单点查询
在这里要引入差分数组d。(即a[]每个元素的增量)
eg:a[1]=1,a[2]=2,a[3]=0
d[1]=a[1]=1, d[2]=a[2]-a[1]=1 ,d[3]=a[3]-a[2]=-2;
那么当我们要做区间[l,r]修改+k时,由于这个区间内的差量是不发生变化的,变化的仅有边界的地方。
因此只要对b[l]+k,b[r+1]-k就能维护区间了。
当我们要查询单点时,可以发现a[x]= $\sum_{i=1}^x {d[i]} \quad$
这样就把单点查询变回上面的区间查询了。
因此我们只需要用树状数组来维护d这个差分数组就行了。
代码就不贴了,因为和上面的那一份是一模一样的。只要刚开始把bit[n]初始化为差分数组即可。
区间修改:对[l,r]的区间+k add(l,k) ,add(r+1,-k);
单点查询(x):a[x]=sum(x);
区间修改+区间查询
区间修改的方式还是可以参照上面差分数组的方法。
区间修改:对[l,r]的区间+k add(l,k) ,add(r+1,-k);
着重来讲一下如何进行区间查询
上面讲了单点查询的方法。
那么不难想到位置p的前缀和:$\sum_{i=1}^p {a[i]} \quad=\sum_{i=1}^p {\sum_{j=1}^i {d[j]} \quad} \quad$
在等式右侧,d[1]被用了p次,d[2]被用了p-1次;
于是可知:
$\sum_{i=1}^p {\sum_{j=1}^i {d[j]} \quad} \quad=\sum_{i=1}^p {d[i]} \quad*(p-i+1) =(p+1)*\sum_{i=1}^p {d[i]} \quad-\sum_{i=1}^p {d[i]*i} \quad$
那么我们接下来只要用两个树状数组去维护d[i]和 d[i]*i 就好了。
c1[i]=d[i];
*c2[i]=d[i]i;
区间查询(l,r):sum(r)- sum(l-1)
贴下代码吧:
|
|