正文

平衡树及笛卡尔树讲解(旋转treap,非旋转treap,splay,替罪羊树及可持久化)

IP云
IP云V管理员/9 阅读
08/22
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

在刷了许多道平衡树的题之后，对平衡树有了较为深入的理解，在这里和大家分享一下，希望对大家学习平衡树能有帮助。

平衡树有好多种，比如treap，splay，红黑树，STL中的set。在这里只介绍几种常用的：treap、splay和替罪羊树(其中treap包括旋转treap和非旋转treap)。

一、treap

treap这个词是由tree和heap组合而成，意思是树上的的堆(其实就是字面意思啦qwq)。treap可以说是由二叉搜索树(BST)进化而来，二叉搜索树每个点满足它左子树中所有点权值都比它小，它右子树中所有点权值都比它大，这样二叉搜索树的中序遍历出来的序列权值就是从小到大有顺序的。对于一棵完全二叉搜索树，查询每个点的时间复杂度是O(logn)。但二叉搜索树很容易就会退化成一条链(顺序或逆序插入所有点)，这样它就失去了原有的作用，于是便有了treap，treap就是在维护BST性质的同时还要维护小根堆(其实大根堆也可以)的性质——每个点的另一个权值比它所有子树上节点的都小，那么这个权值是什么呢？自然是随机数了！只有随机数才能使它成为一棵平衡树(层数在logn层左右)，因为每个点赋值都是随机数，所以对于两个数来说一个点比另一个点大的概率相等。那么怎么同时维护这两种数据结构的性质呢？由此就产生了旋转treap和非旋转treap(具体原理下面再讲)。

treap作为一种平衡树，既可以维护集合，也可以维护序列(splay也同样)。这两者有什么区别呢？维护集合的treap的每个点的权值(具体地说是维护BST性质的权值)是集合中每个数的具体数值，但维护序列的treap的每个点的权值是序列中每个数的下标(也就是这个数在序列中的位置)，而这个数具体是什么不影响平衡树的结构，只是在求解时需要的一个数值。一般维护序列的题刚开始都会先给你一个序列，而维护集合的题每个数都是在过程中插入平衡树中的。

1、旋转treap

旋转treap维护BST和堆的性质是靠旋转实现的，旋转只有两种：左旋和右旋。如图所示。

因为在插入或删除一个数时可能会在树中添加或减掉一个点，所以有可能使treap的性质(具体来说是堆的性质，因为插入时保证按BST性质来插入)不满足或改变树的结构，这时就要用旋转操作来再次恢复treap的性质。旋转treap在维护集合插入时可以把相同权值的的数放在同一个点，也可以建立不同的点来存，如何存要因题而异。

介绍旋转treap的几种常见操作(以相同权值放在同一个点为例)：

变量声明：size[x]，以x为根节点的子树大小；ls[x]，x的左儿子；rs[x]，x的右子树；r[x]，x节点的随机数；v[x]，x节点的权值；w[x]，x节点所对应的权值的数的个数。

1)左旋和右旋

以上图为例，左旋即把Q旋到P的父节点，右旋即把P旋到Q的父节点。

以右旋为例：因为Q>B>P所以在旋转之后还要满足平衡树性质所以B要变成Q的左子树。在整个右旋过程中只改变了B的父节点，P的右节点和父节点，Q的左节点的父节点，与A，B，C的子树无关。

void rturn(int &x)
{
int t;
t=ls[x];
ls[x]=rs[t];
rs[t]=x;
size[t]=size[x];
up(x);
x=t;
}
void lturn(int &x)
{
int t;
t=rs[x];
rs[x]=ls[t];
ls[t]=x;
size[t]=size[x];
up(x);
x=t;
}

2)查询

我们以查询权值为x的点为例，从根节点开始走，判断x与根节点权值大小，如果x大就向右下查询，比较x和根右儿子大小；如果x小就向左下查询，直到查询到等于x的节点或查询到树的最底层。

3)插入

插入操作就是遵循平衡树性质插入到树中。对于要插入的点x和当前查找到的点p，判断x与p的大小关系，决定下一步走向p的左子树还是右子树。如果相同权值的数存入不同点的话，每次插入的点都会插在叶子结点下面。注意在插入后回溯时因为要保证堆的性质，所以要进行左旋或右旋。

void insert_sum(int x,int &i)
{
if(!i)
{
i=++tot;
w[i]=size[i]=1;
v[i]=x;
r[i]=rand();
return ;
}
size[i]++;
if(x==v[i])
{
w[i]++;
}
else if(x>v[i])
{
insert_sum(x,rs[i]);
if(r[rs[i]]<r[i])
{
lturn(i);
}
}
else
{
insert_sum(x,ls[i]);
if(r[ls[i]]<r[i])
{
rturn(i);
}
} return ;
}

4)上传

每次旋转后因为子树有变化所以要修改父节点的子树大小及一些平衡树维护的信息。

void up(int x)
{
size[x]=size[rs[x]]+size[ls[x]]+w[x];
}

5)删除

删除节点的方法和堆类似，要把点旋到最下层再删，如果一个节点w不是1那就把w--就行。

void delete_sum(int x,int &i)
{
if(i==0)
{
return ;
}
if(v[i]==x)
{
if(w[i]>1)
{
w[i]--;
size[i]--;
return ;
}
if((ls[i]*rs[i])==0)
{
i=ls[i]+rs[i];
}
else if(r[ls[i]]<r[rs[i]])
{
rturn(i);
delete_sum(x,i);
}
else
{
lturn(i);
delete_sum(x,i);
}
return ;
}
size[i]--;
if(v[i]<x)
{
delete_sum(x,rs[i]);
}
else
{
delete_sum(x,ls[i]);
}
return ;
}

推荐练习题：

BZOJ3224普通平衡树

NOIP2017列队

BZOJ1208[HNOI2004]宠物收养场

BZOJ1503[NOI2004]郁闷的出纳员

BZOJ3196二逼平衡树

2、非旋转treap

非旋转treap相对于旋转treap更加简单暴力一些，只要断裂和合并两个操作就能维护树的平衡及所有操作(起码我所知的所有操作qwq)，它相对于旋转treap能实现区间操作及可持久化且代码简短(对于我来说是不存在的QAQ)。

介绍一下这两个操作：

1)断裂

就是以一个点为界限，将平衡树分裂成两棵平衡树。注意断裂操作要保证左边平衡树中任意点权值小于右边平衡树中任意点的权值。

以将平衡树分裂成权值<=val和权值>val两部分为例：从根节点开始往下查找，当当前点权值<=val时，将当前点及它的右子树接到分裂后第二棵平衡树的左子树上；反之则将当前点及它的左子树接到分裂后第一棵平衡树的右子树上，直到找到叶子节点为止。

因为分裂后两棵树也要保证平衡树的BST的性质，所以往第一棵树上接节点只能往右子树接，往第二棵树上接节点只能往左子树接。

void split(int x,int &lroot,int &rroot,int val)
{
if(!x)
{
lroot=rroot=0;
return ;
}
if(v[x]<=val)
{
lroot=x;
split(rs[x],rs[lroot],rroot,val);
}
else
{
rroot=x;
split(ls[x],lroot,ls[rroot],val);
}
up(x);
}

2)合并

合并操作和可并堆的合并类似，但可并堆是按左偏树的左偏值来决定当前点是谁，而非旋转treap是按随机数来合并。

void merge(int &x,int a,int b)
{
if(!a||!b)
{
x=a+b;
return ;
}
if(r[a]<r[b])
{
x=a;
merge(rs[x],rs[a],b);
}
else
{
x=b;
merge(ls[x],a,ls[b]);
}
up(x);
}

其他操作只要把treap断裂开，对对应区间或点进行操作再合并回去就OK了。

这样断裂与合并为什么是对的？

从断裂操作的过程我们可以观察到，当这一次走左子树时，将这个点的右子树接到断裂后的第二棵树的左子树上；而走右子树时，则把这个点的左子树接到第一棵树的右子树上。这样保证了断裂后两棵树的BST性质，即一个点的左子树都小于它，右子树都大于它，也保证了第一棵树的所有点都小于第二颗树的所有点。合并时将第一棵树的右子树和第二棵树的左子树合并，因为合并时按每个点赋值的随机数来决定父子关系，所以保证了平衡性。而且合并时遵循第一棵树右子树的点只能是第二棵树左子树点的左儿子或第二棵树左子树的点只能是第一棵树右子树点的右儿子，所以合并后依旧保留了BST的性质。

可持久化：

非旋转treap支持可持久化，可持久化也就是保留历史版本，最暴力的方法就是每一次操作把历史版本的treap复制一遍，然后再在新复制的treap上进行修改，但这样空间时间显然不够。由于非旋转treap没有旋转操作，所以每次操作最多遍历logn个节点，其他节点没有变动，所以只要把遍历的这条链建出来即可。具体操作是在合并和分裂时每遍历到一个节点就要新建一个点复制于当前遍历到的点，然后对新建点再进行递归子树。因为一次操作(例如插入和删除)会多次合并及分裂，空间要远远比nlogn大，所以可以记录每个点所属版本，当一个点要复制于属于同一版本的节点时就可以不再进行复制了，特别地对于区间操作如果需要下传标记也要对标记下传到的点新建点(详情见可持久化文艺平衡树代码)。有人可能会问为什么不能在原版本直接下传再复制？因为标记下传到的点可能是更早版本的点，这样就改变之前版本了，而可持久化需要保留历史版本也就是不对历史版本修改。总而言之就是只要对原版本树的节点信息进行改变时就要新建节点。可持久化平衡树的内存要远远大于其他可持久化数据结构，因此建议数组在不MLE的情况下尽量往大开。

updata：合并时可以不新建节点，因为合并前一定分裂过的，所以对于合并时每层递归到的点在分裂时一定遍历过，而分裂与合并同属一个版本，因此可以将合并时的复制节点操作略去。

附上可持久化普通平衡树模板luoguP3835

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int x,y;
int cnt;
int num;
int r[25000000];
int v[25000000];
int ls[25000000];
int rs[25000000];
int root[8000010];
int size[25000000];
void updata(int x)
{
size[x]=size[ls[x]]+size[rs[x]]+1;
}
void build(int &x,int k)
{
x=++cnt;
v[x]=k;
size[x]=1;
r[x]=rand();
}
void copy(int x,int y)
{
r[x]=r[y];
v[x]=v[y];
ls[x]=ls[y];
rs[x]=rs[y];
size[x]=size[y];
}
int merge(int a,int b)
{
if(!a||!b)
{
return a+b;
}
if(r[a]>r[b])
{
int rt=++cnt;
copy(rt,a);
rs[rt]=merge(rs[rt],b);
updata(rt);
return rt;
}
else
{
int rt=++cnt;
copy(rt,b);
ls[rt]=merge(a,ls[rt]);
updata(rt);
return rt;
}
}
void split(int now,int rt,int &x,int &y)
{
if(!now)
{
x=y=0;
}
else
{
if(v[now]<=rt)
{
x=++cnt;
copy(x,now);
split(rs[x],rt,rs[x],y);
updata(x);
}
else
{
y=++cnt;
copy(y,now);
split(ls[y],rt,x,ls[y]);
updata(y);
}
}
}
void del(int &rt,int v)
{
int x=0;
int y=0;
int z=0;
split(rt,v,x,z);
split(x,v-1,x,y);
y=merge(ls[y],rs[y]);
rt=merge(merge(x,y),z);
}
void insert(int &rt,int v)
{
int x=0;
int y=0;
int z=0;
split(rt,v,x,y);
build(z,v);
rt=merge(merge(x,z),y);
}
int value(int rt,int k)
{
if(k==size[ls[rt]]+1)
{
return v[rt];
}
else if(k<=size[ls[rt]])
{
return value(ls[rt],k);
}
else
{
return value(rs[rt],k-size[ls[rt]]-1);
}
}
int rank(int &rt,int v)
{
int x;
int y;
split(rt,v-1,x,y);
int ans=size[x]+1;
rt=merge(x,y);
return ans;
}
int pre(int &rt,int v)
{
int x;
int y;
int k;
int ans;
split(rt,v-1,x,y);
if(!x)
{
return -2147483647;
}
k=size[x];
ans=value(x,k);
rt=merge(x,y);
return ans;
}
int suf(int &rt,int v)
{
int x;
int y;
int ans;
split(rt,v,x,y);
if(!y)
{
return 2147483647;
}
else
{
ans=value(y,1);
}
rt=merge(x,y);
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&m,&x,&y);
root[i]=root[m];
if(x==1)
{
insert(root[i],y);
}
else if(x==2)
{
del(root[i],y);
}
else if(x==3)
{
printf("%d\n",rank(root[i],y));
}
else if(x==4)
{
printf("%d\n",value(root[i],y));
}
else if(x==5)
{
printf("%d\n",pre(root[i],y));
}
else
{
printf("%d\n",suf(root[i],y));
}
}
}

及可持久化文艺平衡树模板luoguP5055

#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll ans;
ll sum[10000000];
int r[10000000];
int ls[10000000];
int rs[10000000];
int v[10000000];
int s[10000000];
int size[10000000];
int num[10000000];
int a,b,c;
int n,m;
int opt;
int x,y,z;
int cnt;
int root[2000010];
inline int copy(int x,int tim)
{
if(num[x]==tim)
{
return x;
}
int rt=++cnt;
size[rt]=size[x];
sum[rt]=sum[x];
ls[rt]=ls[x];
rs[rt]=rs[x];
r[rt]=r[x];
s[rt]=s[x];
v[rt]=v[x];
num[rt]=tim;
return rt;
}
inline void pushup(int rt)
{
size[rt]=size[ls[rt]]+size[rs[rt]]+1;
sum[rt]=sum[ls[rt]]+sum[rs[rt]]+1ll*v[rt];
}
inline void reverse(int &x,int tim)
{
if(!x)
{
return ;
}
x=copy(x,tim);
swap(ls[x],rs[x]);
s[x]^=1;
}
inline void pushdown(int rt,int tim)
{
if(s[rt])
{
reverse(ls[rt],tim);
reverse(rs[rt],tim);
s[rt]^=1;
}
}
inline int build(int val,int tim)
{
int rt=++cnt;
num[rt]=tim;
v[rt]=val;
size[rt]=1;
r[rt]=rand();
sum[rt]=1ll*v[rt];
return rt;
}
inline int merge(int x,int y,int tim)
{
if(!x||!y)
{
return x+y;
}
int rt;
if(r[x]<r[y])
{
rt=copy(x,tim);
pushdown(rt,tim);
rs[rt]=merge(rs[rt],y,tim);
pushup(rt);
return rt;
}
else
{
rt=copy(y,tim);
pushdown(rt,tim);
ls[rt]=merge(x,ls[rt],tim);
pushup(rt);
return rt;
}
}
inline void split(int rt,int &x,int &y,int k,int tim)
{
if(!rt)
{
x=y=0;
return ;
}
int now=copy(rt,tim);
pushdown(now,tim);
if(size[ls[now]]>=k)
{
y=now;
split(ls[now],x,ls[y],k,tim);
pushup(now);
}
else
{
x=now;
split(rs[now],rs[x],y,k-size[ls[now]]-1,tim);
pushup(now);
}
}
inline void ins(int &rt,int k,int val,int tim)
{
split(rt,a,b,k,tim);
rt=merge(merge(a,build(val,tim),tim),b,tim);
}
inline void del(int &rt,int k,int tim)
{
split(rt,a,b,k-1,tim);
split(b,b,c,1,tim);
rt=merge(a,c,tim);
}
inline void rotate(int &rt,int l,int r,int tim)
{
split(rt,b,c,r,tim);
split(b,a,b,l-1,tim);
reverse(b,tim);
rt=merge(merge(a,b,tim),c,tim);
}
inline ll query(int &rt,int l,int r,int tim)
{
split(rt,b,c,r,tim);
split(b,a,b,l-1,tim);
ll res=sum[b];
rt=merge(merge(a,b,tim),c,tim);
return res;
}
int main()
{
srand(12378);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&m,&opt);
root[i]=root[m];
if(opt==1)
{
scanf("%d%d",&x,&z);
x^=ans;
z^=ans;
ins(root[i],x,z,i);
}
else if(opt==2)
{
scanf("%d",&x);
x^=ans;
del(root[i],x,i);
}
else if(opt==3)
{
scanf("%d%d",&x,&y);
x^=ans;
y^=ans;
rotate(root[i],x,y,i);
}
else
{
scanf("%d%d",&x,&y);
x^=ans;
y^=ans;
ans=query(root[i],x,y,i);
printf("%lld\n",ans);
}
}
}

反向分裂：

在做题的过程中我发现有一些题目用非旋转treap做不了。例如题目要求对编号为x的节点进行操作，这需要你以这个点为界限将平衡树分裂，但你无法通过这个点的权值在平衡树上找到这个点，说简单点也就是你不知道这个点在平衡树中具体在哪。比如：动态维护dfs序，因为插入一个点时会改变后面所有点的dfs序上位置，所以你不能通过dfs序上位置来在平衡树上按size分裂。但splay就能轻松维护了，因为splay旋转时采用的是非递归形式，也就是从操作点出发而不是从平衡树的根节点出发。对比splay的操作方式，我想出了一种由操作点向根节点分裂的方法，也不知道有没有别人也想出过这种方法，我就叫他反向分裂吧。其实就是将正常split反过来操作，多维护一个f[]数组记录每个点的父亲是谁，每次往上爬到父亲，通过判断当前点是父亲的左子树还是右子树来决定将当前点的父节点接到分裂后第一棵平衡树上还是第二棵平衡树上。具体实现看代码。

int merge(int x,int y)
{
if(!x||!y)
{
return x+y;
}
if(r[x]<r[y])
{
rs[x]=merge(rs[x],y);
f[rs[x]]=x;
pushup(x);
return x;
}
else
{
ls[y]=merge(x,ls[y]);
f[ls[y]]=y;
pushup(y);
return y;
}
}
void split(int rt,int &a,int &b)
{
int x=ls[rt];
int y=rs[rt];
ls[rt]=rs[rt]=0;
pushup(rt);
int now=rt;
while(f[rt])
{
if(ls[f[rt]]==rt)
{
ls[f[rt]]=y;
f[y]=f[rt];
y=f[rt];
pushup(f[rt]);
}
else
{
rs[f[rt]]=x;
f[x]=f[rt];
x=f[rt];
pushup(f[rt]);
}
rt=f[rt];
}
f[x]=f[y]=0;
f[now]=0;
a=x;
b=y;
}

注意反向分裂不适用于节点有需下传标记的情况，如果需要下传标记那么依旧要记录每个点的父节点，然后从操作点到根沿途打上一个标记再从根开始正常分裂即可。

推荐练习题：

BZOJ3224普通平衡树

BZOJ3223文艺平衡树

BZOJ1500[NOI2005]维修数列

二、笛卡尔树：

对于一个给定序列建平衡树的时间复杂度是O(nlogn)的，因为每次插入一个数是O(logn)的。这里介绍一种O(n)建树的方法：笛卡尔树。笛卡尔树和treap很相似，都是同时具有二叉搜索树和堆的性质，为了方便我们将二叉搜索树权值称为v1，堆权值称为v2。以维护小根堆为例，在建树时按照v1权值顺序依次插入每个点，这样保证当前点一定是插入到最右边，我们用一个栈依次记录从当前根往下的右子节点(即从根开始一直往右走的所有节点)，依次将v2大于当前插入点的点弹栈，这样就找到了第一个v2比当前插入点小的点p，将p的右子树变为插入点的左子树，然后将插入点变为p的右子树即可。因为每个点只会入栈出栈一次，所以时间复杂度是O(n)的。

注意平衡树建树时要对于每个点pushup(上传信息)。

#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int st[100010];
int v[100010];
int ls[100010];
int rs[100010];
int f[100010];
int top;
int n;
int root;
int build()
{
st[top=1]=1;
for(int i=2;i<=n;i++)
{
while(top&&v[st[top]]>v[i])
{
top--;
pushup(i);
}
if(top)
{
f[i]=st[top];
f[rs[st[top]]]=i;
ls[i]=rs[st[top]];
rs[st[top]]=i;
}
else
{
f[st[1]]=i;
ls[i]=st[1];
}
st[++top]=i;
}
while(top)
{
pushup(st[top]);
top--;
}
return st[1];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
root=build();
}

三、替罪羊树

替罪羊树同样是由一棵BST进化而来，不过它不像treap一样需要随机数来维护树的平衡，它维护平衡的方法更加暴力一些：当对于一个点为根的子树不平衡时就将这棵子树拍扁重构。拍扁重构？就是求出这棵子树的中序遍历然后像线段树一样左右递归建树。那么如何判断一棵树是否平衡呢？我们需要一个平衡因子，一般来说这个因子是0.7~0.9之间的一个浮点数。

重构部分代码。

bool bad(int rt)
{
if(size[rt]*85<=100*max(size[ls[rt]],size[rs[rt]]))
{
return true;
}
return false;
}
void dfs(int rt)
{
if(!rt)
{
return ;
}
dfs(ls[rt]);
if(sig[rt])
{
q[++cnt]=rt;
}
dfs(rs[rt]);
}
void build(int &rt,int l,int r)
{
int mid=(l+r)>>1;
rt=q[mid];
if(l==r)
{
ls[rt]=rs[rt]=0;
size[rt]=tot[rt]=sig[rt]=1;
return ;
}
if(l<mid)
{
build(ls[rt],l,mid-1);
}
else
{
ls[rt]=0;
}
build(rs[rt],mid+1,r);
size[rt]=size[ls[rt]]+size[rs[rt]]+1;
tot[rt]=tot[ls[rt]]+tot[rs[rt]]+1;
}
void rebuild(int &rt)
{
cnt=0;
dfs(rt);
if(cnt)
{
build(rt,1,cnt);
}
else
{
rt=0;
}
}

那么什么时候需要重构呢？当插入一个点时，可能会改变树的平衡，因此在插入节点回溯时我们需要判断回溯到的点的子树是否平衡，如果不平衡就需要重构，但你会发现当前点是否重构不影响回溯到更上面的点对平衡的判断，如果上面还有点需要重构，那么当前点就不用重构了。因此我们只记录离根最近的需要重构的点并进行重构即可，因为重构会改变父子关系，所以建议维护父节点数组来方便重构。替罪羊树的删除有两种方法：1、因为替罪羊树没有旋转操作，所以当删除一个点时就找到这个点的前驱或后继来代替当前点的位置。2、还有一种删除方式是对于要删除的点不直接删除，而是打上标记，当重构时再将被打标记的点丢弃。对于第一种删除方式的重构与插入时重构类似，都是回溯时判断。对于第二种删除方式，我们记录子树实际剩余节点数和包括被打标记的待删除点的节点数，如果这棵子树删除的点数太多了就不平衡了，这个判断平衡方法同样用平衡因子判断。

因为重构后的树高是logn的，所以对于单次操作的时间复杂度是O(logn)，在重构时因为每个点只会被遍历一次，而且重建树时递归分治建树，所以单次复杂度均摊O(logn)。

有人可能会疑惑：为什么平衡因子不设为0.5？因为我们知道重构需要遍历整棵子树，时间复杂度较高，虽然0.5能极大限度的保证查询的时间复杂度但频繁的重构是不划算的，所以0.7~0.9可以在保证查询时间复杂度较为平衡的情况下，减少重构频率，来最小化时间复杂度。

因为其他操作和旋转treap类似，所以在这里就不一一讲解了，直接附上普通平衡树代码。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int ls[400010];
int rs[400010];
int val[400010];
int size[400010];
int sig[400010];
int tot[400010];
int cnt;
int q[400010];
int root;
int n,x;
int opt;
int *point;
int top;
bool bad(int rt)
{
if(size[rt]*85<=100*max(size[ls[rt]],size[rs[rt]]))
{
return true;
}
return false;
}
void dfs(int rt)
{
if(!rt)
{
return ;
}
dfs(ls[rt]);
if(sig[rt])
{
q[++cnt]=rt;
}
dfs(rs[rt]);
}
void build(int &rt,int l,int r)
{
int mid=(l+r)>>1;
rt=q[mid];
if(l==r)
{
ls[rt]=rs[rt]=0;
size[rt]=tot[rt]=sig[rt]=1;
return ;
}
if(l<mid)
{
build(ls[rt],l,mid-1);
}
else
{
ls[rt]=0;
}
build(rs[rt],mid+1,r);
size[rt]=size[ls[rt]]+size[rs[rt]]+1;
tot[rt]=tot[ls[rt]]+tot[rs[rt]]+1;
}
void rebuild(int &rt)
{
cnt=0;
dfs(rt);
if(cnt)
{
build(rt,1,cnt);
}
else
{
rt=0;
}
}
void ins(int &rt,int k)
{
if(!rt)
{
rt=++top;
val[rt]=k;
size[rt]=1;
tot[rt]=1;
sig[rt]=1;
return ;
}
size[rt]++;
tot[rt]++;
if(val[rt]>=k)
{
ins(ls[rt],k);
}
else
{
ins(rs[rt],k);
}
if(bad(rt))
{
point=&rt;
}
}
void clr(int &rt,int k)
{
if(sig[rt]&&size[ls[rt]]+1==k)
{
sig[rt]=0;
size[rt]--;
return ;
}
size[rt]--;
if(size[ls[rt]]+sig[rt]>=k)
{
clr(ls[rt],k);
}
else
{
clr(rs[rt],k-size[ls[rt]]-sig[rt]);
}
}
int rnk(int k)
{
int rt=root;
int ans=1;
while(rt)
{
if(val[rt]>=k)
{
rt=ls[rt];
}
else
{
ans+=size[ls[rt]]+sig[rt];
rt=rs[rt];
}
}
return ans;
}
void del(int k)
{
clr(root,rnk(k));
if(tot[root]*95<=100*size[root])
{
rebuild(root);
}
}
int num(int k)
{
int rt=root;
while(rt)
{
if(sig[rt]&&size[ls[rt]]+1==k)
{
return val[rt];
}
else if(size[ls[rt]]>=k)
{
rt=ls[rt];
}
else
{
k-=sig[rt]+size[ls[rt]];
rt=rs[rt];
}
}
}
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&opt,&x);
if(opt==1)
{
point=0;
ins(root,x);
if(point)
{
rebuild(*point);
}
}
else if(opt==2){del(x);}
else if(opt==3){printf("%d\n",rnk(x));}
else if(opt==4){printf("%d\n",num(x));}
else if(opt==5){printf("%d\n",num(rnk(x)-1));}
else if(opt==6){printf("%d\n",num(rnk(x+1)));}
}
}

四、splay

splay的意思是延展树，同样满足二叉搜索树的性质，只不过splay维护平衡的方法只是旋转。每次查询会调整树的结构，使被查询频率高的条目更靠近树根。因此，就算刚开始时是一条链，在操作过程中也会变成正常的树。

splay一共有六种旋转方式，其中最基础的两种就是treap的那两种，其他四种都是由那两种演化来的。

基础的旋转只能向上转一层，因此有了向上转两层的操作。但转两层自然不会那么简单，旋转是要有顺序的，以上图将x旋到g位置为例，要先将p选上去，再将x旋上去，也就是从上往下旋。双选的方式也是splay保证时间复杂度的根本。

而像这种情况中将x旋到g位置，要先将x旋到p处，再旋到g处，也就是从下往上旋。

splay同样可以实现区间操作且在LCT中会用到，但splay不能可持久化。对于单点操作只需把这个点旋到根节点再查询有关信息即可，对于区间[x,y]操作，先将x-1旋到根节点，再将y+1旋到根节点的右儿子处，这样根节点右儿子的左儿子就是想要的区间。那么如何旋到根节点呢？只要两层两层往上旋就好了。

splay并不是像treap那么平衡，它可能在某一时刻是一条链，但频繁的旋转使它能够达到相对的平衡。splay在建树时建议在最左端和最右端分别建立一个哨兵节点来代表全局最小值和最大值，但注意区间翻转时不要把哨兵节点也跟着翻转了。

最后附上splay区间操作代码(以文艺平衡树区间翻转为例)

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;
int root;
int son[100007][3];
int size[100007];
int val[100007];
int f[100007];
int tag[100007];
int key[100007];
int sum[100007];
int d[100007];
int x,y;
int total;
int INF=1e9;
int flag=0;
bool get(int x)
{
return son[f[x]][1]==x;
}
void pushup(int x)
{
size[x]=size[son[x][0]]+size[son[x][1]]+1;
}
void pushdown(int x)
{
if(x&&tag[x])
{
tag[son[x][0]]^=1;
tag[son[x][1]]^=1;
swap(son[x][0],son[x][1]);
tag[x]=0;
}
}
void rotate(int x)
{
int fa=f[x];
int anc=f[fa];
int k=get(x);
pushdown(fa);
pushdown(x);
son[fa][k]=son[x][k^1];
f[son[fa][k]]=fa;
son[x][k^1]=fa;
f[fa]=x;
f[x]=anc;
if(anc)
{
son[anc][son[anc][1]==fa]=x;
}
pushup(fa);
pushup(x);
}
void splay(int x,int goal)
{
for(int fa;(fa=f[x])!=goal;rotate(x))
{
if(f[fa]!=goal)
{
rotate((get(fa)==get(x))?fa:x);
}
}
if(!goal)
{
root=x;
}
}
int build(int fa,int l,int r)
{
if(l>r)
{
return 0;
}
int mid=(l+r)>>1;
int now=++total;
key[now]=d[mid];
f[now]=fa;
tag[now]=0;
son[now][0]=build(now,l,mid-1);
son[now][1]=build(now,mid+1,r);
pushup(now);
return now;
}
int rank(int x)
{
int now=root;
while(1)
{
pushdown(now);
if(x<=size[son[now][0]])
{
now=son[now][0];
}
else
{
x-=size[son[now][0]]+1;
if(!x)
{
return now;
}
now=son[now][1];
}
}
}
void turn(int l,int r)
{
l=rank(l);
r=rank(r+2);
splay(l,0);
splay(r,l);
pushdown(root);
tag[son[son[root][1]][0]]^=1;
}
void write(int now)
{
pushdown(now);
if(son[now][0])
{
write(son[now][0]);
}
if(key[now]!=-INF&&key[now]!=INF)
{
if(flag==0)
{
printf("%d",key[now]);
flag=1;
}
else
{
printf(" %d",key[now]);
}
}
if(key[son[now][1]])
{
write(son[now][1]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
d[i+1]=i;
}
d[1]=-INF;
d[n+2]=INF;
root=build(0,1,n+2);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
turn(x,y);
}
write(root);
return 0;
}