可以代替线段树的树状数组?——树状数组进阶(1)

树状数组进阶（1） - 前置知识：树状数组，如果没有学过请右转这篇文章：[传送门](https://blog.csdn.net/flushhip/article/details/79165701)，前缀和，差分。 - 本文代码均未经编译，如有错误请指出。 - QQ826755370 ## 引入 大家学了线段树与树状数组后，一定会觉得树状数组比线段树好写~~（背）~~多了，常数也小多了（分析lowbit操作，每次操作中每个节点被访问的概率是1/2,所以常数是1/2）但是美中不足的是树状数组不能区间修改+区间查询啊。事实上，树状数组可以做到这些，还可以查询第k大（小）值。 ## 1、最简单的单点修改+区间查询 这个就不要我讲了吧，直接上代码: ```cpp void add(int pos,int x){ while(pos<=n) c[pos]+=x,pos+=lowbit(pos); } int getsum(int pos){ int sum=0; while(pos) sum+=c[pos],pos-=lowbit(pos); return sum; } ``` ## 2、 稍微难一点点的区间修改+单点0查询 这里用的是差分的思想。 我们设原数组为a，则我们需要维护一个差分数组delta：$delta[i]=a[i]-a[i-1]$ 那么我们可以得到：$a[i]=\sum_{j=1}^idelta[j]$ 现在a[i]被表达成了一个数组内连续的几个元素的，这样我们就解决了查询的问题，那么我们该如何修改呢？ 当我们需要将区间[l,r]上的每个数都加上x时，因为d数组是个差分数组，所以我们可以直接在树状数组上将delta[l]加上x，delta[r+1]减去x即可，代码如下： ```cpp void add(int pos,int x){ while(pos<=n) delta[pos]+=x,pos+=lowbit(pos); } void modify(int l,int r,int x){ add(l,x),add(r+1,-x); } int getsum(int pos){ int sum=0; while(pos) sum+=delta[pos],pos-=lowbit(pos); return sum; } ``` **重点来了！** ## 3、区间修改+区间查询 我们还是需要引入delta数组，这里的delta[i]表示区间a[i...j]都需要加上的值的和。那么当我们需要将区间[l,r]上的每个数都加上x时，我们还是可以直接在树状数组上将delta[l]加上x，delta[r+1]减去x。 那么问题来了，如何查询区间[l,r]的和？ 我们设a[1...i]的和为sum[i]，根据delta数组的定义，则： $$sum[i]=\sum_{j=1}^ia[j]+\sum_{j=1}^idelta[j]*(i-j+1)$$ $$sum[i]=\sum_{j=1}^ia[j]+(i+1)*\sum_{j=1}^idelta[j]-\sum_{j=1}^idelta[j]*j$$ 这样我们就不难看sum[i]是由哪三个部分组成的了。我们需要用一个asum数组维护a数组的前缀和，delta1与delta2两个树状数组，delta1维护delta数组的和，delta2维护delta[i]*i的和，代码如下： ```cpp void add(int *arr int pos,int x){ while(pos<=n) arr[pos]+=x,pos+=lowbit(pos); } void modify(int l,int r,int x){ add(d1,l,x),add(d1,r+1,-x),add(d2,l,x*l),add(d2,r+1,-x*(r+1)); } int getsum(int *arr,int pos){ int sum=0; while(pos) sum+=arr[pos],pos-=lowbit(pos); return sum; } int query(int l,int r){ return asum[r]+r*getsum(d1,r)-getsum(d2,r)-(asum[l-1]+l*getsum(d1,l-1)-getsum(d2,l-1)); } ``` 等等……线段树不是还能查最大最小值吗，事实上树状数组也能查。 ## 4、区间最值 哦，我知道了，我来建树： ```cpp void build(){ for(int i=1;i<=n;i++){ cin>>a[i];int pos=i; while(pos<=n) c[pos]=max(c[pos],a[i]),pos+=lowbit(pos); } } ``` 如果你是这么写的，那么恭喜你……写错了。 以下内容有些难理解，先放一张图：  我们回想一下，当初刚学树状数组时为什么很多人总会说树状数组不能用来求最值。那是因为树状数组可以看作是一种前缀和，求和时可以用ans=ans[r]-ans[l-1]的性质，但是求最值无法满足这种减法的性质。分析一下我们刚才的代码，这么写也不是不对，而是每次查询前都必须初始化，时间复杂度难以接受，让我们换一种写法试一试： ```cpp void build(int n){ for(int i=1;i<=n;i++){ c[i]=a[i],int t=lowbit(i); for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]); } } ``` 现在更新完某个数，之前的元素的值都是正确的了，显而易见，建树的时间复杂度是O(nlogn)的。 那么我们该如何修改呢？当然不能在父亲节点上直接修改啦（手动滑稽），换了一种建树的方式就是为了维护c数组的正确性，修改同样也要保证c数组的正确性，那么在更新父亲节点时，我们就需要查询它所有的儿子节点，代码如下： ```cpp void add(int pos,int x){ a[pos]=x; while(pos<=n){ c[pos]=a[pos];int t=lowbit(i); for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]); pos+=lowbit(pos); } } ``` 不难发现，每层循环都是lowbit操作，时间复杂度为~~O（王逸松）~~O（log(n)*log(n)),其实也没多慢，当n=1e5时，logn约等于16,就把一个logn当成常数看，线段树常数也挺大的啊，树状数组代码量还这么少。 修改是修改完了，那么问题来了，我们该如何查询？ 假设当前查询的区间是[l,r]，那么我们从r到l对每一个c数组的元素所控制的叶子节点进行判断。假设现在进行到了第i项，那么显然易得（看图）：该数控制的a数组的元素是 [i-lowbit(i)+1,i]。设L=i-lowbit(i)+1,R=i。如果l<=L<=r那么就将c[L]加入最值的判断中，接着L--……，否则的话就只对第R个元素加入，然后R--……，代码如下： ```cpp int query(int l,int r){ int ans=a[r]; while(1){ ans=max(ans,num[r]); if(r==l) break; r--; while(r-l>=lowbit(r)) ans=max(ans,c[r]),r-=lowbit(r); //while条件里面的 r-l怎么不写成r-l+1？这才是元素个数啊。 //写r-l+1可能会跳到0，某位大佬试了一下，电脑蓝屏了。 //我也没有试，刨根问底（想要作死）的同学可以自己试一下 } return ans; } ``` 显然，时间复杂度是$O(logn*logn)$的。 完整代码如下： ```cpp void build(int n){ for(int i=1;i<=n;i++){ c[i]=a[i],int t=lowbit(i); for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]); } } void add(int pos,int x){ a[pos]=x; while(pos<=n){ c[pos]=a[pos];int t=lowbit(i); for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]); pos+=lowbit(pos); } } int query(int l,int r){ int ans=a[r]; while(1){ ans=max(ans,num[r]); if(r==l) break; r--; while(r-l>=lowbit(r)) ans=max(ans,c[r]),r-=lowbit(r); } return ans; } ``` ## 5、二维情况下的树状数组 - 单点修改+区间查询 这个我并不想讲，唯一需要注意的点写在注释里了，直接上代码： ```cpp void add(int x,int y,int z){ int t=y;//注意这里需要使用一个变量保存y的值 while(x<=n){ y=t; while(y<=n) c[x][y]+=z,y+=lowbit(y); x+=lowbit(x); } } int getsum(int x,int y){ int ans=0,t=y; while(x){ y=t; while(y) ans+=c[x][y],y-=lowbit(y); x-=lowbit(x); } return ans; } ``` - 区间修改+单点查询 在开始之前，我们先回想一下二维的前缀和如何求和：  这个应该没什么问题吧？ $$sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]$$ 那么我们和一维情形一样，开一个差分数组delta。 $$delta[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$$ 思路到此结束，希望大家可以自己写代码。 - 区间修改+区间查询 这里只给出一句话思路，希望大家自己思考，写出代码。 $$\sum_{i=1}^x\sum_{j=1}^ya[i][j]=\sum_{i=1}^x\sum_{j=1}^y\sum_{k=1}^i\sum_{l=1}^jdelta[k][l]$$ 思路：将以上式子变形成类似一维情形下最终得到的式子。 - 区间最值 有这么毒瘤的题目吗…… ##完结撒花！*★,°*:.☆(￣▽￣)/$:*.°★* 。 ###我的下一篇文章：[可以代替平衡树的树状数组?——树状数组进阶(2)](https://www.luogu.org/blog/Chanis/super-BIT2)