树套树学习笔记

1.例题入门

例题：洛谷传送门 P3380 【模板】二逼平衡树（树套树）

题目大意：维护一个有序数列，其中需要提供以下操作：

查询k在区间内的排名
查询区间内排名为k的值
修改某一位值上的数值
查询k在区间内的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-2147483647)
查询k在区间内的后继(后继定义为严格大于x，且最小的数，若不存在输出2147483647)
时空限制：2s，128M，数据规模：n,m<5*10^4,任意时刻序列元素满足[0,10^8]

2.思路分析

首先，如果只看发现这道题很像平衡树（没学过的可以先看看这篇博客吖~https://www.cnblogs.com/Roysblog/p/13499395.html），但是这道题做了一些变化，询问给定区间内排名为k的树，于是

便想到了维护任意区间的数据结构：线段树。这道题的具体思路是：维护一棵线段树，每个结点用两个参数l,r维护着一段区间，每个结点都是一个Splay旋转平衡树，然后，对于区间询问，我们递归到每个结点

再利用Splay进行计算。

于是，这道题的数据结构便出来了：线段树套平衡树

3.代码：（内含英文注释&&中文注释）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ls(x)  t[x].son[0]  
#define rs(x)  t[x].son[1]  
#define INF 2147483647

using namespace std;

const int N =5e4 + 5;

struct Splay_{
     int size;int tot;int val;int son[2];int fa;
     Splay_(){size=0;tot=0;}
};

struct Seg_tree{
     int l;int r;int root;
};

Splay_ t[50*N];
Seg_tree tr[(N<<2)];

int a[N],n,m,cnt=0;

//**********************Splay平衡树****************************************
inline void push_up(int x)
{t[x].size=t[ls(x)].size+t[rs(x)].size+t[x].tot;}

inline void rotate(int x)
{
    int f=t[x].fa;int g_f=t[f].fa;int locate=(t[f].son[1]==x);
    t[g_f].son[(t[g_f].son[1]==f)]=x;t[x].fa=g_f;
    t[t[x].son[locate^1]].fa=f;t[f].son[locate]=t[x].son[locate^1];
    t[x].son[locate^1]=f;t[f].fa=x;
    push_up(f);push_up(x);
}

inline void Splay(int x,int goal,int Node)
{
    while(t[x].fa!=goal)
    {
        int f=t[x].fa;int g_f=t[f].fa;
        if(g_f!=goal) (t[g_f].son[1]==f)^(t[f].son[1]==x) ? rotate(f) :rotate(x);
        rotate(x);
    }
    if(!goal)  tr[Node].root=x;
}

inline int init(int v,int fa)
{
    t[++cnt].val=v;t[cnt].fa=fa;t[cnt].tot=1;
    push_up(cnt);return cnt;
}

inline void insert(int x,int Node)
{
    int u=tr[Node].root;int fa=0;
    if(!u){u=init(x,0);tr[Node].root=u;return;}
    while(u&&(t[u].val!=x)){fa=u;u=t[u].son[t[u].val<x];}
    if(u&&(x== t[u].val)) t[u].tot++;
    else{u=init(x,fa);if(fa)t[fa].son[t[fa].val<x]=u;}
    
    Splay(u,0,Node);
    
}

inline void find(int x,int Node)
{
    int u=tr[Node].root;
    if(!u) return ;
    while(t[u].son[t[u].val<x] && t[u].val!=x) u=t[u].son[t[u].val<x];
    Splay(u,0,Node);
}

inline int Next(int x,int locate,int Node)
{
    find(x,Node);
    int u=tr[Node].root;
    if((locate&&t[u].val<x)||(!locate&&t[u].val>x)) return u;
    u=t[u].son[locate^1];
    while(t[u].son[locate]) u=t[u].son[locate];
    return u;
}

inline void Del(int x,int Node)
{
    int pre=Next(x,1,Node);int nxt=Next(x, 0, Node);
    Splay(nxt, 0, Node); Splay(pre, nxt, Node);
    int wh = t[pre].son[1];
    if(t[wh].tot > 1) -- t[wh].tot, Splay(wh, 0, Node);
    else t[pre].son[1] = 0;
    push_up(pre); 
}
//**************************************************************************

//***************Segment_tree***********************************************
inline void build(int Node,int l,int r )
{
    insert(INF,Node);insert(-INF,Node);
    if(l==r) return ;
    int mid=((l+r)>>1);
    build((Node<<1),l,mid);build((Node<<1)+1,mid+1,r);
}

inline void Seg_insert(int Node,int l,int r,int k,int val)
{
    int mid=((l+r)>>1);
    insert(val,Node);
    if(l==r) return ;
    if(mid>=k) Seg_insert((Node<<1),l,mid,k,val);
    else   Seg_insert((Node<<1)+1,mid+1,r,k,val);
}

inline int Seg_rank(int Node,int l,int r,int k,int x,int y)
{
    if(l>y||r<x) return 0;
    if(l>=x&&r<=y)
    {
        find(k,Node);int u=tr[Node].root;
        if(t[u].val>=k) return t[ls(u)].size-1;
        else return t[ls(u)].size+t[u].tot-1;
    }
    int mid=((l+r)>>1);
    return Seg_rank((Node<<1),l,mid,k,x,y)+Seg_rank((Node<<1)+1,mid+1,r,k,x,y);
}

inline void Seg_update(int Node,int l,int r,int wh,int val)
{
    Del(a[wh],Node);insert(val,Node);
    if((l==r)&&(l==wh)){a[wh]=val;return ;}
    int mid=((l+r)>>1);
    if(mid>=wh) Seg_update((Node<<1),l,mid,wh,val);
    else Seg_update((Node<<1)+1,mid+1,r,wh,val);
}

inline int  Seg_Pre(int Node,int l,int r,int x,int y,int k)//线段树求前驱 
{
    if(l>y || r<x) return -INF;
    if(l>=x&&r<=y) return t[Next(k,1,Node)].val;
    int mid=((l+r)>>1);
    return max(Seg_Pre((Node<<1),l,mid,x,y,k),Seg_Pre((Node<<1)+1,mid+1,r,x,y,k));
}

inline int Seg_Next(int Node,int l,int r,int x,int y,int k) //线段树里寻找后继 
{
    if(l>y||r<x) return INF;
    if(l>=x&&r<=y) return t[Next(k,0,Node)].val;
    int mid=((l+r)>>1);
    return min(Seg_Next((Node<<1),l,mid,x,y,k),Seg_Next((Node<<1)+1,mid+1,r,x,y,k));
}


inline int Seg_NoK(int x,int y,int k)//求区间内第k大的数 
{
    int l=0,r=1e8,mid=((l+r)>>1),check,ans=0;
    while(l<=r) //二分查找编号 
    {
        mid=((l+r)>>1);
        check=Seg_rank(1,1,n,mid,x,y)+1;
        if(check>k) r=mid-1;
        else {l=mid+1;ans=mid;}
    }
    return ans;
}

//**************Quick_Read**************************************************
inline int Read()
{
    int num=0,k=1;
    char c=getchar();
    while(c!='-'&&(c>'9'||c<'0')) c=getchar();
    if(c=='-'){k=-1;c=getchar();}
    while(c>='0'&&c<='9'){num=(num<<1)+(num<<3)+(c^48);c=getchar();}
    return num*k;
}

//*************************main***************************
int main()
{
    n=Read();m=Read();
    build(1,1,n);int op,l,r,k;
    for(int i=1;i<=n;i++){a[i]=Read();Seg_insert(1,1,n,i,a[i]);}
    for(int i=1;i<=m;i++)
    {
        op=Read();l=Read();r=Read();
        switch(op)
        {
            case 1:{k=Read();printf("%d
",Seg_rank(1,1,n,k,l,r)+1);break;}
            case 2:{k=Read();printf("%d
",Seg_NoK(l,r,k));break;}
            case 3:{Seg_update(1,1,n,l,r);break;}
            case 4:{k=Read();printf("%d
",Seg_Pre(1,1,n,l,r,k));break;}
            case 5:{k=Read();printf("%d
",Seg_Next(1,1,n,l,r,k));break;}
        }
    }
    return 0;
}

洛谷上也有题解，蒟蒻题解大佬指正~（手动ORZ）