树状数组

前言发现，一个点的代表个数为lowbit(x)。\[x=a_0*2^0+a_1*2^1+\ldots+a_{upbit(x)}*2^{upbit(x)} \qquad (a_{n}=1 \mid a_{n}=0)\]至于lowbit()的实现，我们可以用x&-x。有了x&-x，我们就可以用O(logn)的复杂度来查询整个数组。一维功能单点修改，区间查询\[sum[x]=\sum_{i=1}^{x}a[i]\]/*O(logn)*/int t[N];//树状数组void Add(int x,int d)//在第x位加上d{ for(;x<=n;x+=(x&-x) t[x]+=d;}int Ask(int x)//询问前x项的和{ int ans=0; for(;x;x-=(x&-x)) ans+=t[x]; return ans;}Ask(r)-Ask(l-1)//询问[l,r]luogu模板区间修改，单点查询通过差分（就是记录数组中每个元素与前一个元素的差），把问题转化为单点修改，区间查询。z[i]为i与i-1的差分查询\(a[x]=/sum_i=1^xz[i]\)修改[l,r]+d,即为z[l]+=d,z[r+1]-=d;/*O(logn)*/int t[N];void Add(int x,int d){ for(;x<=n;x+=(x&-x)) t[x]+=d;}int Ask(int x){ int ans=0; for(;x;x-=(x&-x)) ans+=t[x]; return ans;}Add(l,d),Add(r+1,-d);//修改[l,r]+dluogu模板区间修改，区间查询基于区间修改，单点查询的差分，z[i]为i与i-1的差分。\[\begin{align*}& \sum_{i=1}^{x}a[i] \\& = \sum_{i=1}^{x}\sum_{j=1}^{i}z[j] \\& = \sum_{i=1}^{x}z[j]*(x-i+1) \\& = (x+1)*\sum_{i=1}^{x}z[i]-\sum_{i=1}^{x}z[i]*i \\\end{align*}\]然后，我们可以维护两个数组的前缀和：一个是\(t[i]=\sum_{j=1}^{i}z[j]\)另一个是\(tr[i]=\sum_{j=1}^{i}z[j]*j\)/*O((logn)^2)*/int t[N],tr[N];void Add(int x,int d){ for(int i=x;i<=n;i+=(i&-i)) t[i]+=d,tr[i]+=d*x;}int Ask(int x){ int ans=0; for(int i=x;i;i-=(i&-i)) ans+=(x+1)*t[i]-tr[i]; return ans;}Add(l,d),Add(r+1,d);//修改[l,r]+d;Ask(r)-Ask(l-1);//查询[l,r];luogu模板二维功能单点修改，区间查询\[sum[x][y]=\sum_{i=1}^{x}\sum_{j=1}^{y}a[i][j]\]/*O(logn*longn)*/int t[N][N];void Add(int x,int y,int d){ for(;x<=n;x+=(x&-x)) for(int i=y;i<=n;i+=(i&-i)) t[x][i]+=d;}int Ask(int x,int y){ int ans=0; for(;x;x-=(x&-x)) for(int i=y;i<=n;i-=(i&-i) ans+=t[i][j]; return ans;}Ask(x,y)+Ask(a-1,b-1)-Ask(x,a-1)-Ask(b-1,y);//查询[a,b]~[x][y] (a<=x&&b<=y)区间修改，单点查询因为二维前缀和为\[sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]\]所以设z[i][j]为a[i][j]与a[i-1][j]+a[i][j-1]-a[i-1][j-1]的差。例如：当我们想把中间的3×3加上d时，差分变化为:实际变化为:查询\(\sum_{i=1}^{x}\sum_{j=1}^{y}z[i][j]\)修改z[a][b]+=d,z[a][y+1]-=d,z[x+1][b]-=d,z[x+1][y+1]+=d; (a<=x&&b<=y)/*O((logn)^2)*/int t[N][N];void Add(int x,int y,int d){ for(;x<=n;x+=(x&-x)) for(int i=y;i<=n;i+=(i&-i)) t[x][i]+=d;}void Ask(int x,int y){ int ans=0; for(;x;x-=(x&-x)) for(int i=y;i;i-=(i&-i)) ans+=t[x][i]; return ans;}Add(a,b,d),Add(a,y+1,-d),Add(x+1,b,-d),Add(x+1,y+1,d);//修改[a,b]~[x,y]+d (a<=x&&b<=y)区间修改，区间查询\[\begin{align*}& \sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{q=1}^{i}\sum_{w=1}^{j}z[q][w] \\& = \sum_{i=1}^{x}\sum_{j=1}^{y}z[i][j]*(x-i+1)*(y-j+1) \\& = \\& (x+1)*(y+1)*\sum_{i=1}^{x}\sum_{j=1}^{y}z[i][j] \\& -(y+1)*\sum_{i=1}^{x}\sum_{j=1}^{y}z[i][j]*i \\& -(x+1)*\sum_{i=1}^{x}\sum_{j=1}^{y}z[i][j]*j \\& +\sum_{i=1}^{x}\sum_{j=1}^{y}z[i][j]*i*j\end{align*}\]所以要开四个数组维护：t[i][j]维护z[i][j]ti[i][j]维护z[i][j]*itj[i][j]维护z[i][j]*jtij[i][j]维护z[i][j]*i*j/*O((logn)^2)*/int t[N][N],ti[N][N],tj[N][N],tij[N][N];void Add(int x,int y,int d){ for(int i=x;i<=n;i+=(i&-i)) for(int j=y;j<=n;j+=(j&-j)) t[i][j]+=d,ti[i][j]+=d*x,tj[i][j]+=d*y,tij[i][j]+=d*i*j;}int Ask(int x,int y){ int ans=0; for(int i=x;i;i-=(i&-i)) for(int j=y;j;j-=(j&-j)) ans+=(x+1)*(y+1)*t[i][j]-(y+1)*ti[i][j]-(x+1)*tj[i][j]+tij[i][j]; return ans;}Add(a,b,d),Add(a,y+1,-d),Add(x+1,b,-d),Add(x+1,y+1,d);//修改[a,b]~[x,y]+d (a<=x&&b<=y)Ask(x,y)+Ask(a-1,b-1)-Ask(x,a-1)-Ask(b-1,y);//查询[a,b]~[x][y] (a<=x&&b<=y)拓展功能不可修改，最大最小树状数组还可以求一个数组的区间中的最大最小。/*O(logn)*/int tmax[N],tmin[N],a[N];memset(tmax,0x80,sizeof(tmax));memset(tmin,0x3f,sizeof(tmin));void Add(int x,int d){ for(;x<=n;x+=(x&-x)) tmax[x]=max(tmax[x],d),tmin[x]=min(tmin[x],d);}递归版本/*O(logn)*/int Fmax(int l,int r){ if(l>=r) return a[l]; if(r-(r&-r)+1>=l) return max(tmax[r],Fmax(l,r-(r&-r))); else return max(a[r],Fmax(l,r-1));}int Fmin(int l,int r){ if(l>=r) return a[l]; if(r-(r&-r)+1>=l) return min(tmin[r],Fmin(l,r-(r&-r)); else return min(a[r],Fmin(l,r-1));}递推版本/*O(logn)*/int Fmax(int l,int r){ int ans=0; while(l<=r) { if(r-(r&-r)+1>=l) ans=max(ans,tmax[r]),r-=(r&-r); else ans=max(ans,a[r]),--r; } return ans;}int Fmin(int l,int r){ int ans=0; while(l<=r) { if(r-(r&-r)+1>=l) ans=min(ans,tmin[r]),r-=(r&-r); else ans=min(ans,a[r]),--r; } return ans;}经验证明递推比递归快，不信可以试试这题，记得用树状数组写。区间固定，第k大小将所有数字看成一个可重集合，即定义数组t[]表示值为x的元素在整个序列重出现了t[x]次。找第k大就是找到最大的x恰好满足\(\sum_{i=1}^xa[i]<k\)。因为在树状数组的结构中，节点是以2的幂的长度划分的，所以我们可以每次扩展2的幂的长度来化简复杂度。最后注意第k大小要加1。这里只列举第k小，因为第k大为第n-k小。/*O(logn)*/int t[N];void Add(int x,int d){ for(x<=n;x+=(x&-x))t[x]+=d;}int Findk(int k){ int ans=0,now=0; for(int i=log2(maxn);i>=0;--i) { ans+=(1<<i); if(ans>tot||now+t[ans]>=k) ans-=(1<<i);//扩展失败 else now+=t[ans];//扩展成功 } return ans+1;}luogu例题离散化后，带权数组有的时候，我们需要用数值做下标，解决这样的问题就是离散化，也就成了带权树状数组。这使空间复杂度由T(maxn)变为T(tot)。/*O(nlogn)*/int n,tot,m[N],a[N];scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d",&a[i]),m[i]=a[i];sort(a+1,a+1+n);tot=unique(a+1,a+n+1)-a-1;//去重for(int i=1;i<=n;++i) m[i]=lower_bound(a+1,a+tot+1,m[i])-a;例如：luogu例题结合动规，数组优化树状数组给动规优化，可使O(n)变为O(logn)。以最长子序列为例：/*O(nlogn)*/int f[N],a[N],t[N],maxans;void Add(int x,int d){ for(;x<=n;x+=(x&-x)) t[x]=max(t[x],d);}int Fmax(int x){ int ans=0; while(l<=r) { if(r-(r&-r)+1<=l) ans=max(ans,t[r]),r-=(r&-r); else ans=max(ans,a[r]),--r; } return ans;}for(int i=1;i<=n;++i){ f[i]=1+Fmax(i); Add(i,f[i]); maxans=max(maxans,f[i]);}printf("%d",maxans);luogu例题优化技巧建树每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。即每次确定完儿子的值后，用自己的值更新自己的直接父亲。这样可把O(nlogn)变为O(n)。/*O(n)*/int a[N],t[N];for(int i=1;i<=n;++i){ scanf("%d",&a[i]); t[i]+=a[i]; if(i+(i&-i)<=n) t[i+(i&-i)]+=t[i]}重建对付多组数据很常见的技巧。如果每次输入新数据时，都memset暴力清空树状数组，就可能会造成超时。因此使用tag标记，存储当前节点上次使用时间（即最近一次是被第几组数据使用）。每次操作时判断这个位置tag中的时间和当前时间是否相同，就可以判断这个位置应该是0还是数组内的值。/*O(logn)*/int tag[N],t[N],Tag;void Add(int x,int d){ for(x<=n;x+=(x&-x)) { if(tag[x]!=Tag) t[x]=0,tag[x]=Tag; t[x]+=d; }}void Ask(int x){ int ans=0; for(;x;x-=(x&-x)) if(tag[x]==Tag) ans+=t[x]; return ans;}++Tag;//重建lougu例题