猫树总结

猫树

这个时候就要\(\texttt{orz immortalCO}\)了。

猫锟的

问题描述

现在你有一些无修改的信息，然后有多组询问，每一次对区间进行询问，信息满足结合律和可交换性。

解法

我们定义一种算法的复杂度为\(O(A)+O(B)+O(C)\)，分别表示预处理复杂度，单次询问复杂度和空间复杂度。

可减信息

直接数组维护。\(O(n)+O(1)+O(n)\)

区间最值

倍增的\(RMQ\)解决即可。\(O(nlogn)+O(1)+O(nlogn)\)

只支持结合律和可交换性

一般采用线段树。\(O(n)+O(logn)+O(n)\)

一种新的解法：猫树

我们仔细思考一下，对于一个点\(o\)而言，如果他需要递归两个儿子等同于\(L\le l \le mid \le r \le R\)。

因为信息满足结合律和可交换律，所以我们只需要对于两边快速合并即可。

然后对于每一层我们可以快速求出点\(i\)对于\(mid\)(\(i<mid\))以及\((i \ge mid)\)的答案。

此时唯一需要的就是快速定位点\(o\)，如果按照一般的线段树建树显然不好定位，但是如果我们建一棵\(2^{k}\)的树，就很容易定位了。

这时我们便找到了一个新的算法：猫树，\(O(nlogn)+O(1)+O(nlogn)\)

看上去很棒！

当然猫树其实只需要保证询问是\(O(1)\)的，只要预处理不超时都还行，所以比较适合那些询问比较多的题目。

GSS1

大致像线段树一样维护\(lmax,rmax,lsum,rsum\)然后合并即可。

附上曾经的题解

/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=200010,Lg=20;
int a[N],n,pos[N],Log[N<<2];
int p[Lg][N],s[Lg][N];
void build(int o,int l,int r,int dep)
{
    if(l==r)
    {
        pos[l]=o;
        return;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid,dep+1);build(o<<1|1,mid+1,r,dep+1);
    p[dep][mid]=s[dep][mid]=a[mid];int sum=a[mid],mx=max(0,a[mid]);
    for(int i=mid-1;i>=l;i--)
    {
        mx+=a[i];sum+=a[i];
        p[dep][i]=max(p[dep][i+1],mx);
        s[dep][i]=max(s[dep][i+1],sum);
        if(mx<0)mx=0;
    }
    p[dep][mid+1]=s[dep][mid+1]=a[mid+1];sum=a[mid+1],mx=max(0,a[mid+1]);
    for(int i=mid+2;i<=r;i++)
    {
        mx+=a[i];sum+=a[i];
        p[dep][i]=max(p[dep][i-1],mx);
        s[dep][i]=max(s[dep][i-1],sum);
        if(mx<0)mx=0;
    }
}
int query(int l,int r)
{
    if(l==r)return a[l];
    int dep=Log[pos[l]]-Log[pos[l]^pos[r]];
    return max(s[dep][l]+s[dep][r],max(p[dep][l],p[dep][r]));
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
#endif
    n=gi();
    for(int i=1;i<=n;i++)a[i]=gi();
    int limit=1;
    while(limit<n)limit<<=1;
    build(1,1,limit,1);int T=gi();
    for(int i=2;i<=limit<<1;i++)Log[i]=Log[i>>1]+1;
    while(T--)
    {
        int l=gi(),r=gi();
        printf("%d\n",query(l,r));
    }
    return 0;
}

题目

剩下的明天补。

猫树总结

原文：https://www.cnblogs.com/mleautomaton/p/11427003.html