一种神奇的数据结构——猫树

猫树是一个有趣的数据结构，之前一直觉得这玩意儿应该很玄学，但学了之后发现还是挺朴素也挺好打的数据结构 →o→[骗访客量](https://www.cnblogs.com/Judge/p/10475728.html) 一、猫树的作用 = 学一个算法当然得先了解它的用处，那么猫树的作用嘛... 简单来讲，线段树能维护的信息猫树基本都能维护 比如什么区间和、区间 gcd 、最大子段和 等 **满足结合律**且**支持快速合并**的信息 二、猫树的算法实现 = 什么都别说，我知道你想先知道猫树是怎么实现的 我们就以区间和查询为例，假设当前查询的区间为 $[~l~,~r~]$ 那么如果我们在此之前预处理过某两个区间的信息，且这两个区间可以合并成当前查询区间，是不是就可以 $O(1)$ 得到答案了呢？ 但是问题就在于如何在一个较短的时间内预处理区间信息，并且使得任意一个区间都能被分成两份预处理过的区间 #### 不扯了，进入正题 1.首先将 1~n 整个区间分成两份 1~mid ， mid+1~n 2.然后对于这两个区间，我们先从中间点 mid 和 mid+1 出发，$O(n)$ 地向两边遍历区间中的每个元素，同时维护要处理的信息 >FAQ:怎么维护？ >这得看你要维护的信息，比如我们举例是区间和，那么处理方式如下： >>对于左边的区间，i 倒序遍历， $f[i]=f[i+1]+a[i]$ >>对于右边的区间，i 正序遍历， $f[i]=f[i-1]+a[i]$ 3.等两个区间都处理完之后，我们再将两个区间继续分下去，重复迭代以上步骤直到区间左右边界重合（即 $l~=~r~$） 接着我们考虑到这样的迭代总共会有 $log~ n$ 层，一个数都会在每一层中都被计算到一次，也就是说**时间复杂度**是 $n~ log~ n$ 的，虽然比不上线段树预处理的线性复杂度，但也已经能够让人接受了 至于空间方面，我们考虑向下迭代的**长度相同**的区间两两不相交，那么他们其实可以存在同一维数组里面，也就是说我们的**空间复杂度**也是 $n~ log~ n $ 的，在承受范围之内 但是这里还有一个问题：如何保证每个区间都能被分成两份预处理过的区间？ 其实我们看到上面的处理方法使得 某个预处理过的区间 可以将任意一个**左右端点都在该区间内**，且**经过该区间中点**的区间分成两份，而这两份区间已经处理过了，那么就可以 $O(1)$ 合并求解了 可能你已经玄学理解了，但是用图还是证明一下好了 ### Proof： 还是画图好...下面是一个不断向下迭代的区间  我们先将查询区间的两个端点表示在总区间上  我们发现这两个点并不能被当前所在区间的中间点分到两边，于是我们将他们下移，那么这两个点就**一起**进入了右区间  我们发现还是他们还是不能被中间点分成两份，继续下移，**一起**进入左区间  可以被分成两份了，那么我们就成功地将该询问区间分成了两个已处理的区间 根本原因我已经在上面加粗了，没错，就是**一起**，如果两个点无法被当前所处区间分到中间点的两边，那么他们必然在该区间的左半部分或者右半部分，那么就可以同时进入某一边的区间了 于是乎得证了... 三、猫树的复杂度分析 = 然后，算法的复杂度总得分析的吧... ## 预处理复杂度 其实这个东西上面讲过了，就是 $O(n log~ n)$ ， 漏看的同学可以翻回去了 ## 询问复杂度 我们发现上面的预处理方式已经满足了我们分割区间的要求，但是... >FAQ:按照上面的找寻分割点的方法，我们发现复杂度好像是 $O(log~ n)$的？ （这不还是线段树的复杂度？） >别急，上面只是证明分割的可行性，并不是找寻分割点的方法 其实不难看出，如果我们让两个点从叶子结点出发，不断向上走知道相遇，那么该区间的中间点就是它们的分割点。 emmm...两个节点不断向上走？这不是 $LCA$ 嘛！那我们就用倍增或者树剖来找$LCA$ ？ 然后我们会发现查询复杂度神奇地变成了 $O(log~log~n)$，已经比线段树强了哈？ 还不够优秀？对，还可以继续优化 之前我们有提到分割点在 $LCA$ 上，那我们可以 $O(1)$ 得到两个节点的 $LCA$ 么？ST表？貌似是可以的哦，但其实不用这么麻烦 我们观察一下就可以发现（或者说根据线段树的性质来说），两个叶子结点的 $LCA$ 的节点编号其实就是他们编号的最长公共前缀（二进制下） ### Eg： 编号为 $(10001)_2 $ 和 $(10110)_2$ 的两个节点的 $LCA$ 编号就是 $(10)_2$ 那么怎么快速求出两个数的最长公共前缀？ 这里要用到非常妙的一个办法： 我们将两个数异或之后可以发现他们的公共前缀不见了，即最高位的位置后移了 $\log LCA.len$ ， 其中 $LCA.len$ 表示 $LCA$ 节点在二进制下的长度 那么我们就可以预处理一下 log 数组，然后在询问的时候就可以快速求出两个询问节点的 $LCA$ 所在的 **层** 了 等等，层？不用求出编号的么？ 那么上面又说过的啊...我们将长度相同的区间放在一维数组里了啊，那么我们又知道这两个区间的左右边界，中间点又是确定的，当然可以在该层中得到我们想要的信息并快速合并起来了（这个的话还是得看代码理解的吧？） #### 综上所述，我们可以在 O(1) 的时间复杂度内查询区间 这复杂度比起线段树都差一个 $log$ 了，一般来讲就是十几倍的时间，然鹅自己造了数据测了测发现两者运行时间仅为两三倍，究其原因的话还是普通线段树的 $log$ 基本是跑不满的（换句话说，我数据造太烂了...） ## 修改复杂度 修改？猫树一般不拿来修改！ 而且也有大佬向我提议说修改没什么用，但我觉得还是讲讲（限制过大，仅供娱乐） 举个例子：有些题目比较毒瘤，可能会给你的操作中大多是查询，少数是**单点修改** 那么完蛋了，猫树能支持修改么？果断弃坑 其实...猫树可以支持吧... 我们在处理的时候用的是一个类似于前缀和的做法，那么前缀和修改的复杂度是多少？（好吧一般来讲带修改就不用前缀和了，这里只是举个例子）， $O(n)$ ！ 那么我们看看一个数在长度为 n/2 、 n/4 、 n/8 .... 1 的区间内被做过前缀和，那么修改的时候也就是要修改这些区间，然后这些区间长度加起来...就是 n 吧？ 然鹅具体的代码实现就不给出了，~~因为我懒~~ 就在这里给个思想，**仅供娱乐** 但是上面讲的是单点修改，区间修改呢？ 这个我真不会，而且也办不到的...讲道理改一次是 $O(n~ log~ n)$ 的吧（相当于重建了），毕竟这也是性质决定的 ~~（区间修改想都别想赶紧弃坑）~~ 四、猫树的代码实现 = 以处理区间最大子段和为例： ```cpp //by Judge #include<cstdio> #include<iostream> #define ll long long using namespace std; const int M=2e5+3; #ifndef Judge #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) #endif char buf[1<<21],*p1=buf,*p2=buf; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char sr[1<<21],z[20];int C=-1,Z; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} inline void print(int x,char chr='\n'){ if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]=chr; } int n,m,len,a[M]; int lg[M<<2],pos[M],p[21][M],s[21][M]; // p 数组为区间最大子段和， s 数组为包含端点的最大子段和 inline int Max(int a,int b){return a>b?a:b;} #define ls k<<1 #define rs k<<1|1 #define mid (l+r>>1) #define lson ls,l,mid #define rson rs,mid+1,r void build(int k,int l,int r,int d){ //这里的边界是叶子结点 //到达叶子后要记录一下 位置 l 对应的叶子结点编号 if(l==r) return pos[l]=k,void(); int prep,sm; // 处理左半部分 p[d][mid]=a[mid], s[d][mid]=a[mid], prep=sm=a[mid],sm=Max(sm,0); for(int i=mid-1;i>=l;--i){ prep+=a[i],sm+=a[i], s[d][i]=Max(s[d][i+1],prep), p[d][i]=Max(p[d][i+1],sm), sm=Max(sm,0); } // 处理右半部分 p[d][mid+1]=a[mid+1], s[d][mid+1]=a[mid+1], prep=sm=a[mid+1],sm=Max(sm,0); for(int i=mid+2;i<=r;++i){ prep+=a[i],sm+=a[i], s[d][i]=Max(s[d][i-1],prep), p[d][i]=Max(p[d][i-1],sm), sm=Max(sm,0); } build(lson,d+1), //向下递归 build(rson,d+1); } inline int query(int l,int r){ if(l==r) return a[l]; int d=lg[pos[l]]-lg[pos[l]^pos[r]]; //得到 lca 所在层 return Max(Max(p[d][l],p[d][r]),s[d][l]+s[d][r]); } int main(){ n=read(),len=2; for(;len<n;len<<=1); for(int i=1;i<=n;++i) a[i]=read();; int l=len<<1; for(int i=2;i<=l;++i) lg[i]=lg[i>>1]+1; build(1,1,len,1); for(int m=read(),l,r;m;--m) l=read(),r=read(), print(query(l,r)); return Ot(),0; } ``` 码量其实会少很多，可以看到最主要的码量就在 $build$ 里面，但是 $build$ 函数的思路还是很清晰的 五、猫树的推荐例题 = [GSS1](https://www.luogu.org/problemnew/show/SP1043) 就是上面的板子 [GSS5](https://www.luogu.org/problemnew/show/SP2916) 不带修改好开森，这题要求最大前缀 、 最大后缀，但是并不影响猫树的发挥 >用了猫树之后直接 $0 ms$ >FAQ：貌似不用也可以啊... >但是猫树码量小吧... >FAQ：不见得啊.... >... 下面是代码（不压行的代码真心打不来） ```cpp //by Judge #include<cstdio> #include<iostream> #define ll long long using namespace std; const int M=2e4+3; #ifndef Judge #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) #endif inline void cmax(int& a,int b){if(a<b)a=b;} inline void cmin(int& a,int b){if(a>b)a=b;} char buf[1<<21],*p1=buf,*p2=buf; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char sr[1<<21],z[20];int C=-1,Z; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} inline void print(int x,char chr='\n'){ if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]=chr; } int n,m,a[M]; namespace cat_tree{ int len,lg[M<<1],pos[M]; int p[16][M],s[16][M],f[16][M],g[16][M]; #define ls k<<1 #define rs k<<1|1 #define mid (l+r>>1) #define lson ls,l,mid #define rson rs,mid+1,r inline int Max(int a,int b){return a>b?a:b;} inline void init(){ for(len=2;len<n;len<<=1); int l=len<<1; for(int i=1;i<=l;++i) lg[i]=lg[i>>1]+1; } void build(int k,int l,int r,int d){ if(l==r) return pos[l]=k,void(); int prep,sm; f[d][mid]=g[d][mid]=a[mid]; p[d][mid]=s[d][mid]=a[mid]; prep=sm=a[mid],sm=Max(sm,0); for(int i=mid-1;i>=l;--i){ prep+=a[i],sm+=a[i],s[d][i]=prep, f[d][i]=Max(f[d][i+1],prep),g[d][i]=sm, p[d][i]=Max(p[d][i+1],sm),sm=Max(sm,0); } f[d][mid+1]=g[d][mid+1]=a[mid+1]; p[d][mid+1]=s[d][mid+1]=a[mid+1]; prep=sm=a[mid+1],sm=Max(sm,0); for(int i=mid+2;i<=r;++i){ prep+=a[i],sm+=a[i],s[d][i]=prep, f[d][i]=Max(f[d][i-1],prep),g[d][i]=sm, p[d][i]=Max(p[d][i-1],sm),sm=Max(sm,0); } build(lson,d+1),build(rson,d+1); } inline int query_sum(int l,int r){ if(l>r) return 0; if(l==r) return a[l]; int d=lg[pos[l]]-lg[pos[l]^pos[r]]; return s[d][l]+s[d][r]; } inline int query_pre(int l,int r){ if(l>r) return 0; if(l==r) return a[l]; int d=lg[pos[l]]-lg[pos[l]^pos[r]]; return Max(s[d][l]+f[d][r],g[d][l]); } inline int query_suf(int l,int r){ if(l>r) return 0; if(l==r) return a[l]; int d=lg[pos[l]]-lg[pos[l]^pos[r]]; return Max(g[d][r],f[d][l]+s[d][r]); } inline int query_mid(int l,int r){ if(l>r) return 0; if(l==r) return a[l]; int d=lg[pos[l]]-lg[pos[l]^pos[r]]; return Max(Max(p[d][l],p[d][r]),f[d][l]+f[d][r]); } } using namespace cat_tree; inline int query(int l1,int r1,int l2,int r2){ int ans; if(r1<l2) return query_sum(r1+1,l2-1)+query_suf(l1,r1)+query_pre(l2,r2); ans=query_mid(l2,r1); if(l1<l2) ans=Max(ans,query_suf(l1,l2)+query_pre(l2,r2)-a[l2]); if(r2>r1) ans=Max(ans,query_suf(l1,r1)+query_pre(r1,r2)-a[r1]); return ans; } int main(){ for(int T=read();T;--T){ n=read(); for(int i=1;i<=n;++i) a[i]=read(); init(),build(1,1,len,1); int l1,r1,l2,r2; for(int m=read();m;--m){ l1=read(),r1=read(), l2=read(),r2=read(), print(query(l1,r1,l2,r2)); } } return Ot(),0; } ``` 其他的能拿来当纯模板的基本找不到（可见限制还是蛮大的，毕竟带修改的不行），不过一些要拿线段树来优化的题目还是可以用上的...~~吧？~~（比如线段树优化 dp ...好像也不行呀，一般线段树优化 dp 不都是带修改的嘛...） 参考资料：[%%% zjp 大佬](https://www.cnblogs.com/zjp-shadow/p/9377742.html) 发明者：[%%% 猫锟 大佬](http://immortalco.blog.uoj.ac/blog/2102)