一种优秀的离线查询数据结构----猫树

前言

　　猫树,由猫锟发明,以简单的构造以及优秀的离线复杂度而出名,可以优秀地处理区间和问题;

　　前置知识:无;

简单思想

　　运用分治的思想,分别处理中点两边的信息,之后分类讨论,合并区间得出结果;

　　保存数据时运用完全二叉树的思想,逐层保存信息,有一定的层次性;

　　例题

　　简单意思即求区间最大和;

　　考虑上面所说的,处理中点两端的信息,即将区间 $的两个端点置于一个中点中间,而这个中点两边的信息我们已经处理过,所以可以分类讨论;$

　　这个是一个简单的图形解释(图画歪了)　　

　　蓝色的查询区间左端点和右端点,红色的是当前区间中点,然后我们将其断开;

　　我们发现查询端点还不在中点两端,那么继续断开;

　　此时我们查询端点就在区间两端了;

　　那么考虑怎么查询,我们可以提前处理出这个区间左半边和右半边的最大区间和,并一起处理出左半边的最大后缀和和右半边的最大前缀和,

　　由于我们的目标区间一定是在左区间或右区间或跨区间,那么如何求出答案就很显然了;

　　根据上面的预处理,我们可以将一个大区间分层,每层分别处理上一层一半的区间,可以分为$logn$层;

　　关于具体操作,这里简述,即从中点向左扫描,向右扫描,求出这个区间左半边和右半边的最大区间和,并一起处理出左半边的最大后缀和和右半边的最大前缀和,

　　关于具体查询

　　如果我们能快速找到这一层,那么就可以$O(1)$更新出结果;

　　很容易发现,左端点(单个点,因为最后我们将区间划分到一个点)和右端点在树中的位置的LCA就是我们想找的那一层;

　　我们很简单可以向上暴力寻找,时间复杂度$O(logn)$;

　　考虑优化,我们可以用倍增或树剖求LCA,这样,我们就可以将时间复杂度优化到$O(loglogn)$的时间复杂度;

　　但是有些不同的是,还记得我在前面说它是一颗完全二叉树,那么每个节点都是上一个节点二进制左移得到的,那么考虑到这一点,我们可以继续优化;

　　例如,$(10011)_2$和$(10101)_2$,这两个节点的LCA是$(10)_2$,很容易发现它就是两点的公共前缀,那么,我们将其异或,就可以将其前缀去掉;

　　那么剩下的$(110)_2$$log2$得到二进制位数,然后原来节点也将其$log2$,得到二进制位数,那么,LCA所在层即为两者相减;

实现

　　上面已经简述了思想,那么代码中我也会有注释,应该很快就能明白,码量较小;

#include<bits/stdc++.h>
#define maxn 50007
#define le(x) x<<1
#define re(x) x<<1|1
using namespace std;
int n,m,cut[25][maxn<<2],cat[25][maxn<<2],dep[maxn<<2],a[maxn<<1];
int pos[maxn<<2];
//cut是记录左区间和右区间最大区间和,cat是记录最大前缀和最大后缀 
template<typename type_of_scan>
inline void scan(type_of_scan &x){
    type_of_scan f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

//预处理 
void Init(int p,int l,int r,int d){
    if(l==r) return pos[l]=p,void();//记录二进制位置 
    int mid=l+r>>1;int pre,con;//pre,con是辅助变量 
    cut[d][mid]=cat[d][mid]=pre=con=a[mid];con=max(con,0);
    for(int i=mid-1;i>=l;i--){
        pre+=a[i],con+=a[i];cat[d][i]=max(cat[d][i+1],pre);
        cut[d][i]=max(cut[d][i+1],con),con=max(con,0);
    }//记录最大后缀, 和左区间的最大区间和 
    cut[d][mid+1]=cat[d][mid+1]=pre=con=a[mid+1];con=max(con,0);
    for(int i=mid+2;i<=r;i++){
        pre+=a[i],con+=a[i];cat[d][i]=max(cat[d][i-1],pre);
        cut[d][i]=max(cut[d][i-1],con),con=max(con,0);
    }//记录最大前缀,和右区间的最大区间和 
    Init(le(p),l,mid,d+1),Init(re(p),mid+1,r,d+1);
}

int query(int l,int r){
    if(l==r) return a[l];
    int d=dep[pos[l]]-dep[pos[l]^pos[r]];//找到深度,即LCA二进制位数 
    return max(max(cut[d][l],cut[d][r]),cat[d][l]+cat[d][r]);
}//分类讨论,比较出结果 

int main(){
    scan(n);int len=2;
    while(len<n) len<<=1;
    for(int i=1;i<=n;i++) scan(a[i]);
    Init(1,1,len,1);//注意,猫树必须是完全二叉树,所以区间长度必须是2的倍数 
    for(int i=2,l=len<<1;i<=l;i++)
        dep[i]=dep[i>>1]+1;//预处理深度,即二进制位数 
    scan(m);
    for(int i=1,l,r;i<=m;i++){
        scan(l),scan(r);
        printf("%d
",query(l,r));
    }
    return 0;
}

应用与拓展

　　猫树限制性比较大,因为它只是支持区间查询,并且查询的东西也有所限制,所以一定要谨慎选择,遇见修改直接改用线段树;

　　有些题线段树优化DP时,可以选择用猫树加快速度,当然也可以根据猫树构造进行一定拓展,这样对分治也有更好地理解.