首页 > 分享 > 猫树简单介绍

猫树简单介绍

萌宠菠菠乐园
2024-10-27 09:06

猫树是一种类似ST表的数据结构，初始化 O(nlog⁡n)" role="presentation">O(nlog⁡n) 查询 O(1)" role="presentation">O(1)，不允许修改（或者说修改代价非常大）

ST表支持的运算要满足可重复贡献，即 x×x=x" role="presentation">x×x=x，比如区间RMQ、区间gcd、区间lcm等

前缀和支持的运算要满足存在逆元（意味着存在逆运算），比如区间和、区间模乘等

而猫树则没有两个限制，猫树支持线段树支持的几乎所有查询操作，除去上述操作外还可以支持矩阵乘法、线性基（ST表也可以线性基但是不能判断是否线性相关）等

我们以ST表模板题为例介绍一下猫树
https://www.luogu.com.cn/problem/P3865

我们先假设n是2的整数次幂，如果不是就要在初始化的时候处理一下

猫树的第0层所有 [i,i]" role="presentation">[i,i] 构成了 n" role="presentation">n 个区间，第1层所有 [2i,2i+1]" role="presentation">[2i,2i+1] 构成了 n2" role="presentation">n2 区间，第2层所有 [4i,4i+3]" role="presentation">[4i,4i+3] 构成了 n4" role="presentation">n4 个区间，依次类推

假设第 s" role="presentation">s 层有一个区间 [l,r]" role="presentation">[l,r]，令它的中点 m=(l+r)/2" role="presentation">m=(l+r)/2，计算区间 [l,m]" role="presentation">[l,m] 的后缀和，存在 cat[s][l...m]" role="presentation">cat[s][l...m] 中；同样计算区间 [m+1,r]" role="presentation">[m+1,r] 的前缀和，存在 cat[s][(m+1)...r]" role="presentation">cat[s][(m+1)...r] 中

比如 n=8" role="presentation">n=8 的情况如下

原数组 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 第0层 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 第1层 [ ] [ ] [ ] [ ] 第2层 [ - - ] [ - - ] 第3层 [ - - - - - - ] 原数组 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 第0层 a[0]" role="presentation">a[0] a[1]" role="presentation">a[1] a[2]" role="presentation">a[2] a[3]" role="presentation">a[3] a[4]" role="presentation">a[4] a[5]" role="presentation">a[5] a[6]" role="presentation">a[6] a[7]" role="presentation">a[7] 第1层 a[0]" role="presentation">a[0] a[1]" role="presentation">a[1] a[2]" role="presentation">a[2] a[3]" role="presentation">a[3] a[4]" role="presentation">a[4] a[5]" role="presentation">a[5] a[6]" role="presentation">a[6] a[7]" role="presentation">a[7] 第2层 a[0]+a[1]" role="presentation">a[0]+a[1] a[1]" role="presentation">a[1] a[2]" role="presentation">a[2] a[2]+a[3]" role="presentation">a[2]+a[3] a[4]+a[5]" role="presentation">a[4]+a[5] a[5]" role="presentation">a[5] a[6]" role="presentation">a[6] a[6]+a[7]" role="presentation">a[6]+a[7] 第3层 a[0]+...+a[3]" role="presentation">a[0]+...+a[3] a[1]+...+a[3]" role="presentation">a[1]+...+a[3] a[2]+a[3]" role="presentation">a[2]+a[3] a[3]" role="presentation">a[3] a[4]" role="presentation">a[4] a[4]+a[5]" role="presentation">a[4]+a[5] a[4]+...+a[6]" role="presentation">a[4]+...+a[6] a[4]+...+a[7]" role="presentation">a[4]+...+a[7]

我们发现对任意的查询区间 [lq,rq]" role="presentation">[lq,rq]，一定存在猫树上的某个区间 [l,r]" role="presentation">[l,r]，[l,r]" role="presentation">[l,r] 包含了 [lq,rq]" role="presentation">[lq,rq] 并且它的中点在 [lq,rq]" role="presentation">[lq,rq] 内

因此我们只要找到这个区间，然后用后缀和+前缀和来计算答案

因为某种巧合，区间 [lq,rq]" role="presentation">[lq,rq] 对应的猫树区间在第 ⌊log2⁡(lq" role="presentation">⌊log2⁡(lq^rq)⌋" role="presentation">rq)⌋ 层内

这里有个小操作，可以用 32-__builtin_clz(x) 代替 ⌊log2⁡(x)⌋" role="presentation">⌊log2⁡(x)⌋（因为我懒得初始化log数组）

猫树的代码量其实还好，也就st表的两三倍

#include <bits/stdc++.h> using namespace std; #define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++) #define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--) typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} const int N=200010; ll in[N]; struct cat{#define U(a,b) max(a,b) //查询操作#define a0 0 //查询操作的零元#define logN 21ll a[logN][N]; //内存等于2^k且大于等于两倍innvoid init(int s,int l,int r){int m=(l+r)/2;repeat_back(i,l,m)a[s][i]=U(a[s][i+1],in[i]);repeat(i,m+2,r+1)a[s][i]=U(a[s][i-1],in[i]);}void init(int inn){ //建树int n; for(n=1;n<inn;n<<=1); repeat(i,inn,n)in[i]=a0;for(int len=1,s=0;len<=n;len<<=1,s++){repeat(i,0,n)a[s][i]=in[i];for(int i=0;i<n;i+=len)init(s,i,i+len-1);}}ll query(int l,int r){ //区间查询int s=32-__builtin_clz(l^r);if(l==r)return a[s][l];else return U(a[s][l],a[s][r]);} }tr; signed main(){//ios::sync_with_stdio(0); cin.tie(0); //freopen("in.txt","r",stdin);int n=read(),m=read();repeat(i,0,n)in[i]=read();tr.init(n);while(m--){int x=read()-1,y=read()-1;printf("%lldn",tr.query(x,y));}return 0; }