一种冷门但是实用的数据结构——猫树浅谈

· · 个人记录

零、前言

在学 \text{OI} 的过程中，你一定会发现一个道理：能支持越多操作的算法，往往就越慢。

让我们来看一个经典例题：

给定一个序列 a_1,a_2,...,a_n，有 T 个询问，每次询问一个区间 [l,r] 的区间最大值。

最方便、简洁的做法毫无疑问是循环暴力，别说一个区间最大值，你想要查询更多东西，还是进行各种修改，无论是单点、区间、隔开还是乱序，都可以使用这种做法。然而这么完美的做法有一个致命的缺点：太 慢 了！

于是人们发明了线段树，这种做法舍弃了小空间、简洁的代码实现，在换取更快的运行时间的同时，也支持了各种常用的操作。有了这样的优点，线段树成了解决这类问题的最常用做法。

但是，如果我还要更快呢？

再一次审视这道题，我们发现，这道题只要求查询，却并不要求修改！那是否意味着，我可以舍弃修改操作，换取查询操作的时间更短？

猫树诞生了。

>因为猫是一种很可爱的生物啊。——$\text{immortalCO}

一、猫树的思想

猫树由 \text{immortalCO} 神犇在 这篇博客 里提出，这是一种基于线段树思想，处理询问支持结合律和快速合并的信息，例如区间最大值、区间 \gcd。考虑使用提前预处理以换取 O(1) 的询问复杂度。

这听上去完全可以用 \text{ST} 表实现，但是 \text{ST} 表的使用需要操作满足可重复贡献，而猫树没有这个限制，可以支持几乎所有线段树支持的东西：例如最大子段和！

二、猫树的实现

假设我们现在要查询的区间为 [l,r]。如果我们可以提前预处理出两段区间，使其合起来可以刚好变成查询区间，那是不是就是 O(1) 的？

预处理的时候，我们将区间一分为二，从中间向两边处理并递归下去。

对于第 num 层，我们处理的是区间每个点到 mid 的前缀/后缀信息，左边处理后缀，右边处理前缀。例如在求区间加法的时候，你的处理应该是:

i \le mid: cat_{num,i}=cat_{num,i+1}+a_i i > mid: cat_{num,i}=cat_{num,i-1}+a_i

一个表格可能会更方便理解：（n=4）

我们发现，对于 [l,r]，我们一定可以在猫树上找到一个点 p，其区间 [ll,rr] 满足 [l,r] 在 [ll,rr] 之中，且 [ll,rr] 的中点 mid 在 [l,r] 內部。

由于我们提前处理了前缀/后缀，所以可以用前缀和与后缀和统计答案。

不难看出，我们的预处理迭代了 \log n 层，其中每一层的处理复杂度 O(n)，因此预处理总复杂度为 O(n \log n)。

但是对于每一次查询来说，如果要找到 p，复杂度似乎还是 O(n \log n)，如何降低？

普通线段树没有什么性质，但是如果这个线段树的点恰好有 2^n 个呢？

这时候我们发现，如果从下往上找，找到它们相遇的点，就是求 \text{LCA} 啊！

接下来就不用说了，树剖或者倍增都可以，时间复杂度 O(n \log \log n)。

慢着，你说的 O(1) 呢？

别急，接下来看 \text{immortalCO} 大佬表演。

观察发现，如果求出了 [ll,rr] 对应的 \text{LCA}，实际上就是节点编号二进制下的 \text{LCP}！

也就是说，一个区间 [ll,rr]，其对应的猫树区间在第 log2(ll^rr) 层。

那么只要 O(n) 预处理出 log2 数组，就可以实现 O(1) 查询啦！

三、猫树的代码模板

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200010;
int n,m;
int a[maxn];
int lg[maxn<<2];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct cat_tree{
    int cat[25][maxn];
    void init_tree(int o,int l,int r){
        int mid=(l+r)>>1;
        for(register int i=mid-1;i>=l;--i) cat[o][i]=max(cat[o][i+1],a[i]);
        for(register int i=mid+2;i<r+1;++i) cat[o][i]=max(cat[o][i-1],a[i]);
    }
    void build_tree(int o){
        int n=1;while(n<o) n<<=1;
        for(register int i=o;i<n;++i) a[i]=0;
        for(register int j=1,cnt=0;j<=n;j<<=1,++cnt){
            for(register int i=0;i<n;++i) cat[cnt][i]=a[i];
            for(register int i=0;i<n;i+=j) init_tree(cnt,i,i+j-1); 
        }
    }
    int query(int l,int r){
        int o=lg[l^r];
        if(l==r) return cat[o][l];
        else return max(cat[o][l],cat[o][r]);
    }
}ct;
inline void init(){
    n=read();m=read();
    for(register int i=1;i<=n;++i) a[i]=read();

    int len=2;while(len<n) len<<=1;
    len<<=1;
    for(register int i=1;i<=len;++i) lg[i]=lg[i>>1]+1;

    ct.build_tree(n+1);
}
signed main(){
    init();
    while(m--){
        int x=read(),y=read();
        printf("%lld\n",ct.query(x,y));
    }
}

四、猫树的习题