猫树分治 | wjyppm's Blog

猫树，整体二分与线段树分治的结合，前者我快忘了，后者更是学都没学过 www。

说人话，就是一种不支持修改，仅仅支持快速区间询问的一种静态线段树。构造要执行 $O(n\log n)$ 次合并操作，而查询可以加速到 $O(1)$ 次合并操作。

猫树问题可以适用于离线解决以下类型的数据结构问题：

与序列有关，且询问是一段区间。
序列静态，即，不涉及修改操作。

当然离不离线都可以，由于其过程类似于点分治，所以在线的情况可通过类似于建出建出点分治的情况动态维护。

我们通过一道例题来进行引入：

给你一个长为 $n$ 的序列 $a$ ，有 $q$ 次询问，每次询问区间 $[l,r]$ 的最大值和最大值个数，可以离线。
$1\le n\le 2\times 10^5,1\le q \le 7\times 10^6,1\le l\le r\le n,1\le a_{i}\le 10^9$ 。

显然你会线段树，但是在 $q\le 7e6$ 的等级下你还是别想了，也就是说我们必须严格 $O(1)$ 回答每一次询问，但是我们预处理的时间复杂度算是比较充裕的 $O(n\log n)$ 。

先离线询问，然后我们考虑一种序列分治的思想，即我们对于一个序列取中点 $mid$ 进行分治，那么会分成 $[l,mid]$ 和 $[mid+1,r]$ 的两个部分。对于询问区间在左部分和右部分的我们可以让递归下去的分治解决。那么现在就剩下一种了，就是跨 $mid$ 的询问区间。

我们考虑怎么处理询问，有一种思路就是我们从 $mid$ 开始，向左预处理后缀最大值数组 $suf$ ，向右预处理前缀最大值数组 $pre$ ，同理最大值个数，这里不再提及。那么我们处理查询的时候只需要将 $suf_{l}$ 和 $pre_{r}$ 的答案合并起来就可以了……没了？

我们分析下复杂度，我们发现每次操作都是 $O(n)$ 的，然后递归复杂度是 $T(n)=2T(n/2)+O(n)$ ，答案是显然的 $O(n\log n)$ ，离线状态下的空间复杂度也是优秀的 $O(\log n)$ ，但每次处理询问是 $O(1)$ 的！

这个就是猫树，我们下面详细解释实现：具体的，考虑分治区间 $[l, r]$ 时，将所有满足 $[L, R] \subseteq [l, r]$ 的区间压入一个 vector。
如果 $l = r$ ，那答案一般是比较好求的，直接算就行了。
否则设 $mid = \left\lfloor \frac{l + r}{2} \right\rfloor$ ，然后对于 $i \in [l, mid]$ 扫一遍处理 $[i, mid]$ 的答案，再对 $i \in [mid + 1, r]$ 扫一遍处理 $[mid + 1, i]$ 的答案，这样处理某个询问 $[L, R]$ 时：

如果 $[L, R] \subseteq [l, mid]$ ，则把它放到左边区间的 vector 里递归；
如果 $[L, R] \subseteq [mid + 1, r]$ ，则把它放到右边区间的 vector 里递归；
如果 $L \in [l, mid], R \in [mid + 1, r]$ ，则将 $[l, mid]$ 和 $[mid + 1, r]$ 的答案合并即可。

不难发现，在上述做法中，我们通过分治把 $\log n$ 的复杂度和单次插入的复杂度摊到了一起，这样每次询问时只用合并一次。如果我们记插入的复杂度为 $T_{\text{insert}}(n)$ ，那么上述算法的复杂度就是： $n \log n \cdot T_{\text{insert}}(n) + q \cdot T_{\text{merge}}(n)$

当然如果强制在线也做得了，直接对每一层分治记录下 $[i, mid], [mid + 1, j]$ 的答案，这样可以做到强制在线，复杂度为： $n \log n \cdot T_{\text{insert}}(n) + q \log n \cdot T_{\text{merge}}(n)$ 当然这种空间可能略有点危，如果记我们单个合并的信息的空间复杂度为 $M(n)$ ，那么该做法空间复杂度为： $n \log n \cdot M(n)$ 。具体的，将序列长度扩充至 $2$ 的幂（维护区间为 $[1, 2^h]$ ），我们考虑将这个区间建成一颗分治树。虽然这是一颗满二叉树，那么我们要找的节点必然是 $[l, l]$ 和 $[r, r]$ 的 LCA。我们采用堆式存储，即节点 $i$ 的左儿子编号为 $2i$ ，右儿子为 $2i+1$ 。观察其二进制形式，不难发现：每一个左儿子的编号相当于父结点编号左移一位，右儿子则是左移一位加一。所以代表 $[l, l]$ 和 $[r, r]$ 这两个区间的两个节点的 LCA 必然是两者编号在二进制下的最长相同前缀（只适用于在同一深度的节点）。至于这两点的编号是多少，我们可以在预处理时提前存储，这样，我们单次查询的时间复杂度为 $O(1)$ 。假设节点编号分别为 $x, y$ ，那么他们的 LCA 编号便是：

x >> \log_2(x \oplus y)

这里 $\log_2[k]$ 存储的是 $k$ 在二进制表示下有多少位。

当然离线询问更好写，这里贴以下来自[数据结构入门]分治树（猫树） - Dfkuaid - 博客园的在线的区间最大子段和：

/*SPOJ GSS1 https://www.spoj.com/problems/GSS1/ */
const int N = 1000100;
const int INF = 0x3fffffff;

int loc[N],a[N],n,m,len = 1;
int s[25][N],p[25][N],lg[N];

/*s 是不能与 mid 断开的前后缀，p 是可与 mid 断开的最大子段*/

inline int Max(const int &a,const int &b){
    return a > b ? a : b;
}

inline void build(int k,int l,int r,int d){
    if (l == r) {loc[l] = k;return;} //叶节点，记录编号
    int mid = (l + r) >> 1;
    int pre,sm;
    /*维护 mid 左边*/
    s[d][mid] = a[mid],p[d][mid] = a[mid];
    pre = sm = a[mid];sm = sm > 0 ? sm : 0;
    for (int i = mid - 1;i >= l;i --){
        pre += a[i],sm += a[i];
        s[d][i] = Max(s[d][i + 1],pre),
        p[d][i] = Max(p[d][i + 1],sm);
        sm = sm > 0 ? sm : 0;
        /*如果小于零了，后面的维护可以
        从中断开，保证最大值*/
    }
    /*维护 mid 右边*/
    s[d][mid + 1] = a[mid + 1],
    p[d][mid + 1] = a[mid + 1];
    pre = sm = a[mid + 1];  sm = sm > 0 ? sm : 0;
    for (int i = mid + 2;i <= r;i ++){
        pre += a[i],sm += a[i];
        s[d][i] = Max(s[d][i - 1],pre);
        p[d][i] = Max(p[d][i - 1],sm);
        sm = sm > 0 ? sm : 0;
    }
    build(k << 1,l,mid,d + 1);
    build(k << 1 | 1,mid + 1,r,d + 1);
}

inline int query(int l,int r){
    if (l == r) return a[l];
    int d = lg[loc[l]] - lg[loc[l] ^ loc[r]];
    return Max(Max(p[d][l],p[d][r]),s[d][l] + s[d][r]);
}

int main(){
    scanf("%d",&n);
    while (len < n) len <<= 1;
    for (int i = 1;i <= n;i ++)
      scanf("%d",&a[i]);
    for (int i = 1;i <= len << 1;i ++)
      lg[i] = lg[i >> 1] + 1;
    build(1,1,len,1);
    scanf("%d",&m);
    while (m --){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));
    }
    return 0;
}

P6240 好吃的题目

猫树分治背包，直接做即可，复杂度是 $O(nV\log n+qV)$ ：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=5e5+15,MV=255;
int suf[MN][MV],pre[MN][MV],n,m,ql[MN],qr[MN],qt[MN],h[MN],w[MN],ans[MN];
vector<int> qry;

void solve(int l,int r,const vector<int> &qry){
    if(!qry.size()) return;
    if(l==r){
        for(auto p:qry){
            if(qt[p]>=h[l]) ans[p]=w[l];
            else ans[p]=0;
        }
        return;
    }
    int mid=(l+r)>>1;
    for(int i=l;i<=r;i++){
        memset(suf[i],0,sizeof(suf[i]));
        memset(pre[i],0,sizeof(pre[i]));
    }
    for(int i=mid;i>=l;i--){
        memcpy(suf[i],suf[i+1],sizeof(suf[i]));
        for(int j=h[i];j<MV;j++){
            suf[i][j]=max(suf[i][j],suf[i+1][j-h[i]]+w[i]);
        }
    }
    for(int i=mid+1;i<=r;i++){
        memcpy(pre[i],pre[i-1],sizeof(pre[i]));
        for(int j=h[i];j<MV;j++){
            pre[i][j]=max(pre[i][j],pre[i-1][j-h[i]]+w[i]);
        }
    }
    vector<int> qryl,qryr;
    for(auto p:qry){
        if(qr[p]<=mid) qryl.push_back(p);
        else if(ql[p]>mid) qryr.push_back(p);
        else{
            for(int i=0;i<=qt[p];i++){
                ans[p]=max(ans[p],suf[ql[p]][i]+pre[qr[p]][qt[p]-i]);
            }
        }
    }
    solve(l,mid,qryl);
    solve(mid+1,r,qryr);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    for(int i=1;i<=m;i++){
        cin>>ql[i]>>qr[i]>>qt[i];
        qry.push_back(i);
    }
    solve(1,n,qry);
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<'\n';
    }
    
    
    return 0;
}

P6109 [Ynoi2009] rprmq1

先考虑没有修改怎么做，用 ST 表或者二维 BIT 简单维护即可。考虑有单点修改怎么做，ST 表当场坠机不过二维 BIT 还建在！考虑区间修改怎么做，发现极其难以直接进行维护。

注意到题目可以离线，而且一个很神秘的一点就是修改操作时小于查询的操作的，同时如果不仔细看，难发现所有查询操作在修改操作之后！

我们考虑这个矩形加 $v$ 的操作怎么维护，我们发现这个玩意可以扫描线，例如 $(l1,r1,l2,r2,v)$ 操作，可以对 $[l1,r1]$ 进行扫描线，实现中我们将询问转化为两个区间端点上的修改即可，用历史和线段树维护 $[l2,r2]$ 的范围，用历史和是因为我们求得是矩形最大值，用历史最大值可以表示一个矩形面内的答案。

但是问题在于如果我们要求的是一个时间段内的信息，历史和最大值比较难以做到多次撤销回退，快速对一个时间段求历史最大值做不了，但是可以对一个时间 $l$ 开始往后求 $[l,r]$ 时间中的历史最大值。

考虑猫树分治，具体的，我们将所有询问对应的 $l1,r1$ 挂到猫树上，从 mid 开始正反做两遍历史最大值即可求出所有挂在该节点的询问答案。具体的就是我们现将 $[l,mid]$ 的操作加入，在 $mid+1$ 时刻清空历史最大值，从 $[mid+1,r]$ 开始做历史最大值，并处理对应询问。接着猫树上递归 $[mid+1,r]$ 。对于左边 $[l,mid]$ 同样不过就是反过来了，注意撤销 $[mid+1,r]$ 的遗留答案，时间复杂度 $O(m\log^2 n+(n+q)\log n)$ 。