伸展树(Splay)
- 算法思想
- 左旋&右旋
- 伸展
- 查找
- 插入
- 分裂
- 合并
- 删除(指节点值)
- 区间操作
- 训练
- POJ3481
- HDU3487
- POJ3580
- HDU4453
- 总结
算法思想
Splay是根据数据局部性的特点所得出的算法,数据局部性包括时间局部性和空间局部性
时间局部性: 刚刚被访问的元素,极有可能在不久后再次被访问
空间局部性: 刚刚被访问的元素,其相邻节点也有可能被访问
Splay的无需时刻保持全树平衡,其单次搜索也可能到达n次操作,但是可以保证m次操作下连续搜索的复杂度为 O ( m log n ) O(m\log n) O(mlogn),Splay不需要记录平衡因子,树高,子树大小等额外信息,适用范围更广
AVL为了严格保持平衡,在调整时会对树有过多的旋转操作,影响了性能,而Splay在每次操作后都会将刚被访问的节点旋至树根,加速后续的操作,这样查询频率高的节点经常靠近树根,所需要的旋转也就更少
左旋&右旋
伸展操作Splay(x,goal)是在保持有序性前提下,通过一系列旋转将伸展树中元素x调整到goal的子节点,若goal为0则x旋转到树根,旋转有左旋与右旋
右旋,如图,节点p右旋时,会携带其右子树,向右旋转到q的右子树位置,q的右子树放在p的左子树位置,旋转后的树根为q
左旋,节点q左旋,携带其左子树,左旋转到p的左子树位置,p的左子树放在q的右子树位置,旋转后树根为q
在伸展树中,左旋与右旋代码相同,相比较于Treap,其节点存储方式有所不同,详见代码
代码
void Rotate(int x)
{
int y=tr[x].fa,z=tr[y].fa;//记录两个节点的父节点
int c=(tr[y].son[0]==x);//判断x是y的右子还是左子
tr[y].son[!c]=tr[x].son[c];//将x另一个子连接到y上
tr[tr[x].son[c]].fa=y;//同上
tr[x].fa=z;
if(z)
tr[z].son[tr[z].son[1]==y]=x;//将x与z连接
tr[x].son[c]=y;
tr[y].fa=x;
}
伸展
伸展方式有两种,一种为逐层伸展(低效),另一种为双层伸展(高效)
逐层伸展
伸展操作是伸展树的灵魂所在,对于函数Rotate(x),前文已经讲过,而伸展操作正是以此操作为基础加以实现的,其函数大多命名为Splay(x,goal)
为了使x旋转到目标goal之下,逐层伸展的思路为:若x的父节点不为goal,则判断x为其父节点的左/右子节点,则执行x右/左旋,直到x的父节点为目标,特别的,当目标为0时,x变为树根
代码
void Splay(int x,int goal)
{
while(tr[x].fa!=goal) Rotate(x);
if(!goal) root=x;
}
双层伸展
逐层伸展容易理解,代码也很简单,但是在最坏情况下,每次访问的时间复杂度都为 O ( n ) O(n) O(n),双层拓展在逐层拓展的基础上优化了一些,每次向上追溯两层,判断旋转类型并进行相应的旋转,时间复杂度平摊可以达到 O ( log n ) O(\log n) O(logn)
双层伸展每次都向上追溯两层,旋转类型有三种情况
- Zig/Zag,即只进行一次旋转,若x的父节点y为根,那么直接根据x为y的左/右子来右/左旋即可,图略
- Zig-Zig/Zag-Zag,即进行两次相同性质的旋转,但是与逐层伸展不同的是,双层伸展是先从上进行旋转,再旋转当前层,以左旋-左旋为例,如图
- Zig-Zag/Zag-Zig,即两次不同性质的旋转,这里和逐层拓展相同,在此不赘述
Splay的时间复杂度证明较为复杂,也不是重点,详情参考
Splay的时间复杂度的一种证明
伸展树(Splay)复杂度证明
关于双层拓展能够减小树高的例子详见
伸展树学习笔记之双层伸展
在了解了双层拓展的具体分类与操作之后,便可以参考逐层拓展给出代码
代码
void Splay(int x,int goal)
{
while(tr[x].fa!=goal)
{
int y=tr[x].fa,z=tr[y].fa;//获得上两层
if(z!=goal)//第二和第三种情况
(tr[z].son[0]==y)^(tr[y].son[0]==x)?Rotate(x):Rotate(y);//异或运算,如果性质相同直接转y
Rotate(x);
}
if(!goal)root=x;//直接转到根了
}
查找
伸展树的查找就和二叉搜索树的查找方式大同小异了,只不过每次需要将找到的值拓展到树根
代码
bool Find(int val)
{
int x=root;
while(1)
{
if(val==tr[x].val)//如果找到
return 1;
if(tr[x].son[tr[x].val<val])//这里是个很巧妙的写法,直接精简了代码,代表入左或入右
x=tr[x].son[tr[x].val<val];
else return 0;
}
}
插入
与二叉搜索树的插入类似,也是需要每次把最新插入的值伸展到根
代码
int New(int x,int val)
{
tr[++cnt].fa=x;
tr[cnt].son[0]=tr[cnt].son[1]=0;
tr[cnt].val=val;
return cnt;
}
void Insert(int val)
{
int x=root;
for(;tr[x].son[tr[x].val<val];x=tr[x].son[tr[x].val<val]);//找到插入的位置
tr[x].son[tr[x].val<val]=New(x,val);//开新点
Splay(tr[x].son[tr[x].val<val],0);//新节点转树根
}
分裂
分裂操作为伸展树的一大特点,形式上类似点分治,以某一点的权值将整棵伸展树分成两半,首先找到该点,之后直接将该点伸展为树根,删去树根即可
代码
bool Split(int val,int &l,int &r)
{
if(Find(val))
{
l=tr[root].son[0];
r=tr[root].son[1];
tr[l].fa=tr[r].fa=0;
return 1;
}
return 0;
}
合并
与分裂相对应的操作即为合并,望文生义,合并即将两个伸展树合并成一个,但需要保证左树的所有值小于右树,首先找到左树的最大值并伸展至树根,之后直接将右树与最大值连接即可
代码
void FindMax()
{
int x=root;
while(tr[x].son[1])
x=tr[x].son[1];
if(x)Splay(x,0);
}
void Join(int l,int r)
{
if(l)
{
FindMax();//找到最大值并向上伸展到树根
tr[root].son[1]=r;
tr[r].fa=root;
}
else//左树为空
root=r;
}
删除(指节点值)
删除某个值只需要将其伸展到根节点,之后去掉根然后合并左右子树即可
代码
void Delete(int val)
{
int l=0,r=0;
if(Split(val,l,r))
Join(l,r);
}
区间操作
当伸展树中节点的值为序列中每个元素的位置,则可以使用伸展树代替线段树并且可以实现线段树无法实现的删除区间和插入区间的功能,在这里只给出思路,具体相关实现参考例题
删除区间: 删除[l,r]区间内所有元素首先找到l-1的位置,将l-1的节点旋转到树根然后找到r+1,将r+1旋转到树根的右子,删去r+1的左子
插入区间: 在给定的位置k之后插入一些值,假设这些值的序列为 { a 1 , a 2 , … , a n } \{a_1,a_2,\dots,a_n\} {a1,a2,…,an},将序列构成伸展树t,将位置k旋转到根,将k+1旋转到k的右子,将t插入k+1左子即可
训练
POJ3481
题目大意:略
思路:本题涉及到插入,删除最高和最低三种操作,可以用伸展树来实现
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
//#include <unordered_map>
#include <map>
#include <set>
#include <numeric>
#include <stack>
#include <sstream>
#include <cmath>
#include <bitset>
//#include <unordered_set>
#include <functional>
#include <list>
#include <vector>
#include <iterator>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 Bint;
const int maxn=1e7+10;
int cnt,root;
struct tree {
int son[2],val,fa,num;//左右子,值,父,编号
} tr[maxn];
int New(int x,int val,int num) {//添加新节点
tr[++cnt].val=val;
tr[cnt].num=num;
tr[cnt].fa=x;
tr[cnt].son[0]=tr[cnt].son[1]=0;
return cnt;
}
void Rotate(int x) {//左旋右旋
int y=tr[x].fa,z=tr[y].fa;
int c=(tr[y].son[0]==x);
tr[y].son[!c]=tr[x].son[c];
tr[tr[x].son[c]].fa=y;
tr[x].fa=z;
if(z)tr[z].son[tr[z].son[1]==y]=x;
tr[x].son[c]=y;
tr[y].fa=x;
}
void Splay(int x,int goal) {//双层拓展
while(tr[x].fa!=goal) {
int y=tr[x].fa,z=tr[y].fa;
if(z!=goal) (tr[z].son[0]==y)^(tr[y].son[0]==x)?Rotate(x):Rotate(y);
Rotate(x);
}
if(!goal)root=x;//这里设置了根节点
}
void Insert(int val,int num) {
int x=root;
for(; tr[x].son[tr[x].val<val]; x=tr[x].son[tr[x].val<val]);
tr[x].son[tr[x].val<val]=New(x,val,num);//这里可能更改了0号位置的左右子树
Splay(tr[x].son[tr[x].val<val],0);
}
void Delete(int x) {//删除的对象均为最左或最右节点,所以必有一子为空
if(x==root) {
if(!tr[x].son[0]&&!tr[x].son[1]) {
cnt=root=0;
tr[0].son[0]=tr[0].son[1]=0;//不加这个会超时
} else {
int t=tr[x].son[0]?0:1;//判断哪棵树不为空
tr[tr[x].son[t]].fa=0;//去掉根节点,上提一个点
root=tr[x].son[t];
}
} else {
int y=tr[x].fa,t=(tr[y].son[1]==x);
tr[y].son[t]=tr[x].son[!t];//把对应的非空子上提即可
tr[tr[x].son[!t]].fa=y;
Splay(y,0);
}
}
void PrintMax() {
int x=root;
while(tr[x].son[1])
x=tr[x].son[1];
cout <<tr[x].num<<endl;
Delete(x);
}
void PrintMin() {
int x=root;
while(tr[x].son[0])
x=tr[x].son[0];
cout <<tr[x].num<<endl;
Delete(x);
}
int main() {
ios::sync_with_stdio(0),cin.tie();
int t,k,p;
while(cin >>t&&t) {
switch(t) {
case 0:
return 0;
break;
case 1:
cin >>k>>p;
Insert(p,k);
break;
case 2:
PrintMax();
break;
case 3:
PrintMin();
break;
}
}
return 0;
}
HDU3487
题目大意:初始一个1 ~ n的有序序列,两种操作:CUT a b c 将区间[a,b]切下街道剩余区间的第c个之后 FLIP a b 将区间[a,b]翻转
思路:利用伸展树的区间操作的性质实现题设要求,具体看代码
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <unordered_map>
#include <map>
#include <set>
#include <numeric>
#include <stack>
#include <sstream>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <functional>
#include <list>
#include <vector>
#include <iterator>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Bint;
const int maxn=1e6+10;
int cnt,n,m,root;
bool flag;
struct node {
int son[2],val,fa,s,rev;//左右子,值,父,规模,翻转标记
} tr[maxn];
int New(int f,int val) {//添加新节点
tr[++cnt].fa=f;
tr[cnt].rev=0;
tr[cnt].son[0]=tr[cnt].son[1]=0;
tr[cnt].val=val;
tr[cnt].s=1;
return cnt;
}
void Update(int x) {
tr[x].s=1;
if(tr[x].son[0])
tr[x].s+=tr[tr[x].son[0]].s;
if(tr[x].son[1])
tr[x].s+=tr[tr[x].son[1]].s;
}
void PushDown(int x) {//下传翻转标记
if(tr[x].rev) {
tr[x].rev^=1;
swap(tr[x].son[0],tr[x].son[1]);
if(tr[x].son[0])
tr[tr[x].son[0]].rev^=1;
if(tr[x].son[1])
tr[tr[x].son[1]].rev^=1;
}
}
void Rotate(int x) { //旋转
PushDown(x);
int y=tr[x].fa,z=tr[y].fa;
int c=(tr[y].son[0]==x);
tr[y].son[!c]=tr[x].son[c];
tr[tr[x].son[c]].fa=y;
tr[x].fa=z;
if(z)tr[z].son[tr[z].son[1]==y]=x;
tr[x].son[c]=y;
tr[y].fa=x;
Update(y);
Update(x);
}
void Splay(int x,int goal) {//双层拓展
while(tr[x].fa!=goal) {
int y=tr[x].fa,z=tr[y].fa;
if(z!=goal) (tr[z].son[0]==y)^(tr[y].son[0]==x)?Rotate(x):Rotate(y);
Rotate(x);
}
if(!goal)root=x;//这里设置了根节点
}
void Build(int l,int r,int &t,int fa) {//建伸展树
if(l>r)return ;
int mid=(l+r)>>1;
t=New(fa,mid);
Build(l,mid-1,tr[t].son[0],t);
Build(mid+1,r,tr[t].son[1],t);
Update(t);
}
void Init() {//初始化
cnt=root=0;//根节点设置为0
tr[0].son[0]=tr[0].son[1]=0;//左右清空
root=New(0,-maxn);//插入无穷小
tr[root].son[1]=New(root,maxn);//插入无穷大
tr[root].s=2;//更新大小
Build(1,n,tr[tr[root].son[1]].son[0],tr[root].son[1]);//建伸展树
Update(tr[root].son[1]);//更新无限大子树大小
Update(root);//更新大小
flag=1;
}
int Findk(int x,int k) {//查找第k个元素
while(1) {
PushDown(x);//下推
int sn=tr[x].son[0]?tr[tr[x].son[0]].s+1:1;//左子树不空,获得左子树的规模,否则只获得1
if(k==sn)return x;//正好左子树的大小与k相同
if(k>sn)k-=sn,x=tr[x].son[1];//如果排名大于左子树规模,直接入右子树,但是要减小排名
else x=tr[x].son[0];//
}
}
void Cut(int l,int r,int c) { //将[l,r]区间切割,插入第c个节点之后
int x=Findk(root,l-1),y=Findk(root,r+1);
Splay(x,0),Splay(y,x);
int t=tr[y].son[0];
tr[y].son[0]=0;//清空,相当于删除
Update(y),Update(x);
x=Findk(root,c),y=Findk(root,c+1);
Splay(x,0),Splay(y,x);
tr[y].son[0]=t;
tr[t].fa=y;
Update(y),Update(x);
}
void Flip(int l,int r) {
int x=Findk(root,l-1),y=Findk(root,r+1);//找到区间左前一个,找到区间右后一个
Splay(x,0),Splay(y,x);//伸展
tr[tr[y].son[0]].rev^=1;//左子树区间翻转
}
void Print(int k) {
PushDown(k);
if(tr[k].son[0])
Print(tr[k].son[0]);
if(tr[k].val!=-maxn&&tr[k].val!=maxn) {
if(flag)
cout <<tr[k].val,flag=0;
else
cout <<" "<<tr[k].val;
}
if(tr[k].son[1])
Print(tr[k].son[1]);
}
int main() {
ios::sync_with_stdio(0),cin.tie();
while(cin >>n>>m&&n>0&&m>0) {
Init();
int a,b,c;
string s;
while(m--) {
cin >>s;
if(s=="CUT") {
cin >>a>>b>>c;
Cut(a+1,b+1,c+1);
} else if(s=="FLIP") {
cin >>a>>b;
Flip(a+1,b+1);
}
}
Print(root);
cout <<endl;
}
return 0;
}
POJ3580
题目大意:给定一个初始序列 A 1 , A 2 , A 3 , … , A n A_1,A_2,A_3,\dots ,A_n A1,A2,A3,…,An,一共6种操作:ADD x y D 对区间[x,y]都增加D;REVERSE x y 翻转区间[x,y];REVOLVE x y T 旋转子序列[x,y]T次(等同于将[x,y]循环右移T次);INSERT x P 在 A x A_x Ax后插入P;DELETE x 删除第x个值;MIN x y 查询[x,y]的最小值
思路:本题涉及到插入、删除、区间的查+改+翻+旋,使用伸展树
关于虚节点: 处理 [ l , r ] [l,r] [l,r]区间时经常需要将 A l − 1 A_{l-1} Al−1旋转到根,然后将 A r + 1 A_{r+1} Ar+1旋转到 A l − 1 A_{l-1} Al−1下方,但如果操作的是整个区间,那么 [ l − 1 , r + 1 ] [l-1,r+1] [l−1,r+1]这个区间是不存在的,所以需要添加虚节点,一个为 − i n f -inf −inf,另一个为 i n f inf inf,由于在序列前添加了虚节点,之后操作的区间变为了 [ l + 1 , r + 1 ] [l+1,r+1] [l+1,r+1]
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
//#include <unordered_map>
#include <map>
#include <set>
#include <numeric>
#include <stack>
#include <sstream>
#include <cmath>
#include <bitset>
//#include <unordered_set>
#include <functional>
#include <list>
#include <vector>
#include <iterator>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=4e6+10;
int cnt,root,a[maxn],n,m;
struct node {
int val,son[2],s,f,add,minv,rev;//值,左右,规模,父,增加标记,最小值,翻转标记
} tr[maxn];
int New(int fa,int val) {
tr[++cnt].f=fa;
tr[cnt].val=val;
tr[cnt].rev=tr[cnt].son[0]=tr[cnt].son[1]=tr[cnt].add=0;
tr[cnt].minv=val;//注意初始化
tr[cnt].s=1;
return cnt;
}
void PushDown(int x) {
if(tr[x].rev) {//下传翻转
tr[x].rev^=1;
swap(tr[x].son[0],tr[x].son[1]);//翻转
if(tr[x].son[0])tr[tr[x].son[0]].rev^=1;
if(tr[x].son[1])tr[tr[x].son[1]].rev^=1;
}
if(tr[x].add) {//下传添加
if(tr[x].son[0]) {
tr[tr[x].son[0]].val+=tr[x].add;
tr[tr[x].son[0]].add+=tr[x].add;
tr[tr[x].son[0]].minv+=tr[x].add;
}
if(tr[x].son[1]) {
tr[tr[x].son[1]].val+=tr[x].add;
tr[tr[x].son[1]].add+=tr[x].add;
tr[tr[x].son[1]].minv+=tr[x].add;
}
tr[x].add=0;//清空
}
}
void Update(int x) {
tr[x].minv=tr[x].val;
tr[x].s=1;//初始化规模
if(tr[x].son[0]) {//左存在
tr[x].s+=tr[tr[x].son[0]].s;
tr[x].minv=min(tr[x].minv,tr[tr[x].son[0]].minv);
}
if(tr[x].son[1]) {//右存在
tr[x].s+=tr[tr[x].son[1]].s;
tr[x].minv=min(tr[x].minv,tr[tr[x].son[1]].minv);
}
}
void Build(int l,int r,int &t,int fa) {//构建平衡树
if(l>r)return ;
int mid=(l+r)>>1;
t=New(fa,a[mid]);
Build(l,mid-1,tr[t].son[0],t);
Build(mid+1,r,tr[t].son[1],t);
Update(t);
}
void Init() {//初始化
cnt=root=0;
tr[0].son[0]=tr[0].son[1]=0;
root=New(0,-maxn);//虚节点1
tr[root].son[1]=New(root,maxn);//虚节点2
tr[root].s=2;
Build(1,n,tr[tr[root].son[1]].son[0],tr[root].son[1]);//范围,构造的开始点,父节点
Update(tr[root].son[1]);
Update(root);
}
void Rotate(int x) {//重要
PushDown(x);
int y=tr[x].f,z=tr[y].f;
int c=tr[y].son[0]==x;
tr[y].son[!c]=tr[x].son[c];
tr[tr[x].son[c]].f=y;
tr[x].f=z;
if(z)tr[z].son[tr[z].son[1]==y]=x;
tr[x].son[c]=y;
tr[y].f=x;
Update(y);
Update(x);
}
void Splay(int x,int goal) {
while(tr[x].f!=goal) {
int y=tr[x].f,z=tr[y].f;
if(z!=goal)(tr[z].son[0]==y)^(tr[y].son[0]==x)?Rotate(x):Rotate(y);
Rotate(x);
}
if(!goal)root=x;
}
int Findk(int x,int k) {
while(1) {
PushDown(x);//一定要下推
int sn=tr[x].son[0]?tr[tr[x].son[0]].s+1:1;
if(k==sn)
return x;
if(k<sn)
x=tr[x].son[0];
else
k-=sn,x=tr[x].son[1];
}
}
void Insert(int pos,int val) {
int x=Findk(root,pos),y=Findk(root,pos+1);
Splay(x,0),Splay(y,x);
tr[y].son[0]=New(y,val);
Update(y),Update(x);
}
void Delete(int k) {
int x=Findk(root,k-1),y=Findk(root,k+1);
Splay(x,0),Splay(y,x);
tr[y].son[0]=0;
Update(y),Update(x);
}
int GetMin(int l,int r) {
int x=Findk(root,l-1),y=Findk(root,r+1);
Splay(x,0),Splay(y,x);
Update(y),Update(x);//这里可以不用
return tr[tr[y].son[0]].minv;
}
void Add(int l,int r,int d) {
int x=Findk(root,l-1),y=Findk(root,r+1);
Splay(x,0),Splay(y,x);
tr[tr[y].son[0]].add+=d;
tr[tr[y].son[0]].val+=d;
tr[tr[y].son[0]].minv+=d;
Update(y),Update(x);
}
void Reverse(int l,int r) {
int x=Findk(root,l-1),y=Findk(root,r+1);
Splay(x,0),Splay(y,x);
tr[tr[y].son[0]].rev^=1;
}
void Revolve(int l,int r,int t) {
t%=r-l+1;//区间取余
if(t==0)return ;
int x=Findk(root,r-t),y=Findk(root,r+1);//获得边界
Splay(x,0),Splay(y,x);
int tmp=tr[y].son[0];
tr[y].son[0]=0;
Update(y),Update(x);
x=Findk(root,l-1),y=Findk(root,l);//同上
Splay(x,0),Splay(y,x);//必须旋转
tr[y].son[0]=tmp;
tr[tmp].f=y;
Update(y),Update(x);
}
int main() {
//ios::sync_with_stdio(0),cin.tie();
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",a+i);
Init();
scanf("%d",&m);
getchar();
while(m--) {
int a,b,c;
char t[20];
scanf("%s",t);
if(strcmp(t,"ADD")==0) {
scanf("%d%d%d",&a,&b,&c);
Add(a+1,b+1,c);
}
if(strcmp(t,"REVERSE")==0) {
scanf("%d%d",&a,&b);
Reverse(a+1,b+1);
}
if(strcmp(t,"REVOLVE")==0) {
scanf("%d%d%d",&a,&b,&c);
Revolve(a+1,b+1,c);
}
if(strcmp(t,"INSERT")==0) {
scanf("%d%d",&a,&b);
Insert(a+1,b);
}
if(strcmp(t,"DELETE")==0) {
scanf("%d",&a);
Delete(a+1);
}
if(strcmp(t,"MIN")==0) {
scanf("%d%d",&a,&b);
printf("%d\n",GetMin(a+1,b+1));
}
getchar();
}
return 0;
}
HDU4453
题目大意:对一个循环队列进行增删查,区间增加,区间翻转,指针左移右移(等价于切割后插入)
思路:建伸展树,将待查询保持为第二个位置(因虚节点而增加),指针左移等价于 A n A_n An头插,指针右移等价于 A 1 A_1 A1尾插
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <unordered_map>
#include <map>
#include <set>
#include <numeric>
#include <stack>
#include <sstream>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <functional>
#include <list>
#include <vector>
#include <iterator>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Bint;
const int maxn=1e6+10;
int n,m,k1,k2,cnt,root,sum,a[maxn];
char op[20];
struct node {
int val,s,son[2],add,rev,f;
} tr[maxn];
int New(int fa,int val) {
tr[++cnt].val=val;
tr[cnt].f=fa;
tr[cnt].rev=tr[cnt].son[0]=tr[cnt].son[1]=tr[cnt].add=0;//清空
tr[cnt].s=1;
return cnt;
}
void Update(int x) {
tr[x].s=1;
if(tr[x].son[0])
tr[x].s+=tr[tr[x].son[0]].s;
if(tr[x].son[1])
tr[x].s+=tr[tr[x].son[1]].s;
}
void PushDown(int x) {
if(tr[x].rev) {
tr[x].rev^=1;
swap(tr[x].son[0],tr[x].son[1]);
if(tr[x].son[0])tr[tr[x].son[0]].rev^=1;
if(tr[x].son[1])tr[tr[x].son[1]].rev^=1;
}
if(tr[x].add) {
if(tr[x].son[0]) {
tr[tr[x].son[0]].add+=tr[x].add;
tr[tr[x].son[0]].val+=tr[x].add;
}
if(tr[x].son[1]) {
tr[tr[x].son[1]].add+=tr[x].add;
tr[tr[x].son[1]].val+=tr[x].add;
}
tr[x].add=0;
}
}
void Rotate(int x) {
PushDown(x);
int y=tr[x].f,z=tr[y].f;
int c=tr[y].son[0]==x;
tr[y].son[!c]=tr[x].son[c];
tr[tr[x].son[c]].f=y;
tr[x].f=z;
if(z)tr[z].son[tr[z].son[1]==y]=x;
tr[x].son[c]=y;
tr[y].f=x;
Update(y);
Update(x);
}
void Splay(int x,int goal) {
while(tr[x].f!=goal) {
int y=tr[x].f,z=tr[y].f;
if(z!=goal)(tr[z].son[0]==y)^(tr[y].son[0]==x)?Rotate(x):Rotate(y);
Rotate(x);
}
if(!goal)root=x;
}
int Findk(int x,int k) {
while(1) {
PushDown(x);
int sn=tr[x].son[0]?tr[tr[x].son[0]].s+1:1;
if(sn==k)return x;
if(sn>k)x=tr[x].son[0];
else k-=sn,x=tr[x].son[1];
}
}
void Insert(int pos,int val) {
int x=Findk(root,pos),y=Findk(root,pos+1);
Splay(x,0),Splay(y,x);
tr[y].son[0]=New(y,val);
Update(y),Update(x);
sum++;
}
int Delete(int pos) {
int x=Findk(root,pos-1),y=Findk(root,pos+1);
Splay(x,0),Splay(y,x);
int t=tr[tr[y].son[0]].val;
tr[y].son[0]=0;
Update(y),Update(x);
sum--;
return t;
}
void Build(int l,int r,int &t,int fa) {
if(l>r)return ;
int mid=(l+r)>>1;
t=New(fa,a[mid]);
Build(l,mid-1,tr[t].son[0],t);
Build(mid+1,r,tr[t].son[1],t);
Update(t);//更新
}
void Init() {
cnt=root=0;
tr[0].son[0]=tr[0].son[1]=0;
root=New(0,-maxn);
tr[root].son[1]=New(root,maxn);
tr[root].s=2;
Build(1,n,tr[tr[root].son[1]].son[0],tr[root].son[1]);
Update(tr[root].son[1]);
Update(root);
}
void Add(int l,int r,int val) {
int x=Findk(root,l-1),y=Findk(root,r+1);
Splay(x,0),Splay(y,x);
tr[tr[y].son[0]].add+=val;
tr[tr[y].son[0]].val+=val;
Update(y),Update(x);
}
void Reverse(int l,int r) {
int x=Findk(root,l-1),y=Findk(root,r+1);
Splay(x,0),Splay(y,x);
tr[tr[y].son[0]].rev^=1;
}
int main() {
ios::sync_with_stdio(0),cin.tie();
int cas=0,x;
while(~scanf("%d%d%d%d",&n,&m,&k1,&k2)) {
if(n==0)break;
printf("Case #%d:\n",++cas);
for(int i=1; i<=n; i++)
scanf("%d",a+i);
Init();
sum=n;
while(m--) {
scanf("%s",op);
switch(op[0]) {
case 'a':
scanf("%d",&x);
Add(2,k2+1,x);
break;
case 'r':
Reverse(2,k1+1);
break;
case 'i':
scanf("%d",&x);
Insert(2,x);
break;
case 'd':
Delete(2);
break;
case 'm':
scanf("%d",&x);
if(x==1) {
int y=Delete(sum+1);
Insert(1,y);
} else {
int y=Delete(2);
Insert(sum+1,y);
}
break;
case 'q':
printf("%d\n",tr[Findk(root,2)].val);
break;
}
}
}
return 0;
}
总结
伸展树的作用范围很广,在某些情况下甚至可以代替线段树,伸展树最突出的特点就是区间操作:区间翻转,区间插入,区间删除,与其他二叉搜索树相比它能使得总体时间效率得到平摊,使得总效率为 O ( m log n ) O(m\log n) O(mlogn),当操作涉及到以区间为单位的位置变动时,就会使用到伸展树
更多推荐
伸展树(Splay)
发布评论