猫树的简单介绍

猫树是一种类似 ST 表的数据结构，初始化 $O(n\log n)$ 查询 $O(1)$ ，不允许修改（或者说修改代价非常大）。

ST表支持的运算要满足可重复贡献，即 $x\times x=x$ ，比如区间 RMQ、区间 gcd、区间 lcm 等。

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

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

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

猫树的第 0 层所有 $[i,i]$ 构成了 $n$ 个区间，第1层所有 $[2i,2i+1]$ 构成了 $\dfrac n 2$ 区间，第2层所有 $[4i,4i+3]$ 构成了 $\dfrac n 4$ 个区间，依次类推。

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

比如 $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]$	$a[1]$	$a[2]$	$a[3]$	$a[4]$	$a[5]$	$a[6]$	$a[7]$
第1层	$a[0]$	$a[1]$	$a[2]$	$a[3]$	$a[4]$	$a[5]$	$a[6]$	$a[7]$
第2层	$a[0]+a[1]$	$a[1]$	$a[2]$	$a[2]+a[3]$	$a[4]+a[5]$	$a[5]$	$a[6]$	$a[6]+a[7]$
第3层	$a[0]+...+a[3]$	$a[1]+...+a[3]$	$a[2]+a[3]$	$a[3]$	$a[4]$	$a[4]+a[5]$	$a[4]+...+a[6]$	$a[4]+...+a[7]$

我们发现对任意的查询区间 $[l_q,r_q]$ ，一定存在猫树上的某个区间 $[l,r]$ ， $[l,r]$ 包含了 $[l_q,r_q]$ 并且它的中点在 $[l_q,r_q]$ 内。

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

因为某种巧合，区间 $[l_q,r_q]$ 对应的猫树区间在第 $\lfloor\log_2(l_q$ ^ $r_q)\rfloor$ 层内。

这里有个小操作，可以用 32-__builtin_clz(x) 代替 $\lfloor\log_2(x)\rfloor$ （~~因为我懒得初始化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 21
    ll a[logN][N]; //内存等于2^k且大于等于两倍inn
    void 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("%lld\n",tr.query(x,y));
    }
    return 0;
}

← Codeforces 1305 题解 (A-G) 不平等博弈的 Q & A→