首页 > 分享 > 猫树学习笔记

猫树学习笔记

萌宠菠菠乐园
2024-10-05 02:51

猫树是什么？

猫树，是 immortalCO 在这篇文章提出的一种类似线段树的数据结构。猫树可以处理支持结合律的信息，如区间最大值、区间最大子段和、区间等。在维护的信息可以合并时，猫树能用预处理，查询的时间复杂度，的空间复杂度解决序列上在线静态区间查询问题。

猫树怎么实现？

看一个例题：GSS1 - Can you answer these queries I。

静态区间最大子段和，典中典，相信大家都会用线段树做。那猫树怎么做？

考虑先像线段树一样建树。对于树上每个节点，令，我们在这个节点上维护表示，表示，表示间的最大子段和，表示间的最大子段和。显然这个预处理是的，空间也是的。

在查询区间时，我们发现只要找到一个点，满足且猫树上存在一个区间满足且，我们就可以把最大子段和分成过和不过两种，答案就是。而这个区间其实就是在线段树上的对应点的。但是如果暴力查的话单次询问复杂度还是的，怎么办？

immortalCO 指出，我们可以类似 zkw 线段树那样，把猫树扩充到个点形成一颗满二叉树。那么所对应的两个节点的，也就是两个位置对应节点的编号的二进制数的 LCP！而获得的二进制的 LCP 只需要使用 x>>(Log2[x^y]+1)，线性预处理 Log2 就得到了一种查询的优秀算法。

在写的时候，我们不用真的对每个点开一个 vector 来存储信息，也不需要精确定位到节点上。由于每层维护的信息是不交的，只需要对每层开一个数组，询问时定位的深度。

给出例题的代码。

点击查看代码

#include<bits/stdc++.h> #define int long long using namespace std; const int inf=1e18; inline int read(){int x=0,f=1;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f; } int a[70005],Log[140005]; struct CatTree{int loc[70005],sum[18][70005],ans[18][70005];void build(int n,int d){for(int i=1;i<=n;i++)loc[i]=i+n-1;for(int len=2,o=d-1;len<=n;len<<=1,o--){for(int l=1;l<=n;l+=len){int r=l+len-1,mid=(l+r)>>1;sum[o][mid]=a[mid],sum[o][mid+1]=a[mid+1];for(int i=mid-1;i>=l;i--)sum[o][i]=sum[o][i+1]+a[i];for(int i=mid+2;i<=r;i++)sum[o][i]=sum[o][i-1]+a[i];for(int i=mid-1;i>=l;i--)sum[o][i]=max(sum[o][i],sum[o][i+1]);for(int i=mid+2;i<=r;i++)sum[o][i]=max(sum[o][i],sum[o][i-1]);ans[o][mid]=a[mid],ans[o][mid+1]=a[mid+1];for(int i=mid-1;i>=l;i--)ans[o][i]=max(ans[o][i+1],0ll)+a[i];for(int i=mid+2;i<=r;i++)ans[o][i]=max(ans[o][i-1],0ll)+a[i];for(int i=mid-1;i>=l;i--)ans[o][i]=max(ans[o][i+1],ans[o][i]);for(int i=mid+2;i<=r;i++)ans[o][i]=max(ans[o][i-1],ans[o][i]);}}}int ask(int l,int r){if(l==r)return a[l];int o=Log[loc[l]]-Log[loc[l]^loc[r]]-1;return max({ans[o][l],ans[o][r],sum[o][l]+sum[o][r]});} }Tr; signed main(){int n=read(),len=1,dep=0;while(len<n)len<<=1,dep++;for(int i=1;i<=n;i++)a[i]=read();Log[1]=0;for(int i=2;i<=len<<1;i++)Log[i]=Log[i>>1]+1;Tr.build(len,dep);int q=read();for(int i=1,l,r;i<=q;i++)l=read(),r=read(),printf("%lldn",Tr.ask(l,r));return 0; }

几道其他例题：

GSS5 - Can you answer these queries V

猫树分治是什么？

猫树分治只与猫树在思想上有相似之处。考虑一些可以离线的问题，假设当前有一堆询问区间和当前的状态区间。取状态区间的中点，从开始向左右分别预处理一些信息。然后把所有询问分成三部分：如果，我们递归到状态区间解决；如果，我们递归到状态区间解决；否则说明跨过，可以合并左右信息解决。复杂度与预处理的复杂度有关。

猫树分治怎么实现？

一道简单例题：P6240 好吃的题目

区间 01 背包，直接做很困难。考虑猫树分治，每次预处理从区间中点往左右两边延伸的背包，求答案时枚举一边的体积。

点击查看代码

#include<bits/stdc++.h> #define int long long using namespace std; const int inf=1e18,V=200; inline int read(){int x=0,f=1;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f; } int n,m,h[40005],w[40005],ql[200005],qr[200005],qt[200005],q[200005],ans[200005],f[205][40005]; void solve(int l,int r,int lq,int rq){if(l==r){for(int i=lq;i<=rq;i++)ans[q[i]]=(h[l]<=qt[q[i]]?w[l]:0);return;}int mid=(l+r)>>1;for(int i=l;i<=r;i++){for(int j=0;j<=V;j++)f[j][i]=0;}for(int i=h[mid];i<=V;i++)f[i][mid]=w[mid];for(int i=mid-1;i>=l;i--){for(int j=V;j>=h[i];j--)f[j][i]=max(f[j][i+1],f[j-h[i]][i+1]+w[i]);for(int j=h[i]-1;j>=0;j--)f[j][i]=f[j][i+1];}for(int i=h[mid+1];i<=V;i++)f[i][mid+1]=w[mid+1];for(int i=mid+2;i<=r;i++){for(int j=V;j>=h[i];j--)f[j][i]=max(f[j][i-1],f[j-h[i]][i-1]+w[i]);for(int j=h[i]-1;j>=0;j--)f[j][i]=f[j][i-1];}vector<int>L,R;for(int i=lq;i<=rq;i++){if(qr[q[i]]<mid+1)L.push_back(q[i]);else if(ql[q[i]]>mid)R.push_back(q[i]);else{for(int j=0;j<=qt[q[i]];j++)ans[q[i]]=max(ans[q[i]],f[j][ql[q[i]]]+f[qt[q[i]]-j][qr[q[i]]]);}}int lt=lq-1;for(auto x:L)q[++lt]=x;int rt=lt;for(auto x:R)q[++rt]=x;solve(l,mid,lq,lt);solve(mid+1,r,lt+1,rt); } signed main(){n=read(),m=read();for(int i=1;i<=n;i++)h[i]=read();for(int i=1;i<=n;i++)w[i]=read();for(int i=1;i<=m;i++)ql[i]=read(),qr[i]=read(),qt[i]=read(),q[i]=i;solve(1,n,1,m);for(int i=1;i<=m;i++)printf("%lldn",ans[i]);return 0; }

又一道简单例题：P7482 不条理狂诗曲

定义表示左边到，选/不选的最大价值，表示右边到，选/不选的最大价值。考虑怎么求。整体提一个就变成了，令，，可以分别对排序，双指针做一下即可。复杂度，换成基排应该就是了吧。

点击查看代码

#include<bits/stdc++.h> #define int long long using namespace std; const int inf=1e18,mod=1e9+7; inline int read(){int x=0,f=1;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f; } int n,ans,a[100005],f[100005][2],F[100005],G[100005],s[100005]; void solve(int l,int r){if(l==r){ans=(ans+a[l])%mod;return;}int mid=(l+r)>>1;f[mid][0]=0,f[mid][1]=a[mid];f[mid-1][0]=a[mid-1],f[mid-1][1]=a[mid];for(int i=mid-2;i>=l;i--){f[i][0]=max(f[i+1][0],f[i+2][0]+a[i]);f[i][1]=max(f[i+1][1],f[i+2][1]+a[i]);}f[mid+1][0]=0,f[mid+1][1]=a[mid+1];f[mid+2][0]=a[mid+2],f[mid+2][1]=a[mid+1];for(int i=mid+3;i<=r;i++){f[i][0]=max(f[i-1][0],f[i-2][0]+a[i]);f[i][1]=max(f[i-1][1],f[i-2][1]+a[i]);}for(int i=l;i<=mid;i++)F[i]=max(0ll,f[i][1]-f[i][0]),ans=(ans+f[i][0]*(r-mid)%mod)%mod;for(int i=mid+1;i<=r;i++)G[i]=max(0ll,f[i][1]-f[i][0]),ans=(ans+f[i][0]*(mid-l+1)%mod)%mod;sort(F+l,F+mid+1);sort(G+mid+1,G+r+1);s[r]=G[r];for(int i=r-1;i>=mid+1;i--)s[i]=s[i+1]+G[i];for(int i=l,j=mid;i<=mid;i++){while(j+1<=r&&F[i]>=G[j+1])j++;if(j==r)ans=(ans+F[i]*(r-mid)%mod)%mod;else ans=(ans+F[i]*(j-mid)%mod+s[j+1])%mod;}solve(l,mid);solve(mid+1,r); } signed main(){n=read();for(int i=1;i<=n;i++)a[i]=read();solve(1,n);printf("%lldn",ans);return 0; }

几道其他例题：

P4755 Beautiful Pair

CF1100F. Ivan and Burgers

P6009 [USACO20JAN] Non-Decreasing Subsequences P

卡空间题。