學完Splay的查找作用，發現和普通的二叉查找樹沒什麼差別，隻是用了splay操作節省了時間開支。
而Splay序列之王的稱号可不是白給的。
Splay真正強大的地方是他的區間操作。
怎麼實作呢？
我們知道查找樹的中序周遊是一個有序的序列。這個時候我們打破查找樹左小右大的規則，而是把他的中序周遊作為我們的區間進行維護。
具體來講有以下操作：
1、建樹
2、區間操作【翻轉、指派啊什麼的】
3、輸出序列
建樹
既然是區間，我們可以借鑒線段樹的建樹
void build(int& u,int l,int r,int fa)
{
if(l>=r) return;
u=++siz;
int mid=(l+r)>>1;
e[u].v=mid;
e[u].siz=1;
e[u].f=fa;
if(l+1<r)
{
build(e[u].ch[0],l,mid,u);
build(e[u].ch[1],mid+1,r,u);
e[u].siz+=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz;
}
}
就用遞歸從中間建起
區間操作
我們想要從樹中找到我們需要的區間,怎麼辦呢? 這個時候就是發揮Splay威力的時候了> < Splay的伸展操作【也就是splay操作】可以在不改變中序周遊的前提下改變樹的結構，也就是說我們可以在不改變序列的前提下改變樹的形态。 那麼這個時候，如果我們要操作區間[l,r]我們隻需将l-1翻轉到根節點，将r+1翻轉到根節點的右兒子 這個時候想想，r+1的左子樹是什麼？ 沒錯！就是我們要的區間[l,r]
怎麼找到這兩個節點？ 就套用splay中的查找第k大節點就好了【其實在這裡不能說是第k大，是第k個】
但是我們如果要操作[1,N]怎麼辦？ 我們加一個0和N+1節點不就好啦【哨兵】
至于找到區間後怎麼操作，就因題而異啦，一般都會加上一個lazy标記節省時間 附上splay操作
#define isr(x) (e[e[x].f].ch[1]==x)
...........
inline void spin(int u)
{
int fa=e[u].f,s=isr(u);
e[u].f=e[fa].f;
if(e[fa].f) e[e[fa].f].ch[isr(fa)]=u;
e[fa].ch[s]=e[u].ch[s^1];
e[fa].f=u;
if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;
e[u].ch[s^1]=fa;
up(fa);up(u);
}
void splay(int u,int fa=0)
{
while(e[u].f!=fa)
{
if(e[e[u].f].f&&lazy[e[e[u].f].f]) pd(e[e[u].f].f);
if(lazy[e[u].f]) pd(e[u].f);
if(lazy[u]) pd(u);
if(e[e[u].f].f==fa) spin(u);
else if(isr(u)^isr(e[u].f)) spin(u),spin(u);
else spin(e[u].f),spin(u);
}
if(!fa) root=u;
}
其中lazy是打的标記，splay的時候記得下傳【凡是涉及到兒子的操作都要考慮标記下傳】 pd是标記下傳函數
輸出序列
其實就是中序周遊嘛，自己打【其實是我懶】
來道裸題： 洛谷P3391 文藝平衡樹
裸的區間翻轉
#include<iostream>
#include<cstdio>
#include<algorithm>
#define isr(x) (e[e[x].f].ch[1]==x)
using namespace std;
const int maxn=200005,INF=2000000000;
int N,M;
inline int read()
{
int out=0,flag=1;char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57){out=out*10+c-48;c=getchar();}
return out*flag;
}
int lazy[maxn];
class node
{
public:
int v,ch[2],f,siz;
node() {ch[0]=ch[1]=0;siz=0;}
}e[maxn];
int siz=0,root=0;
inline void up(int u){e[u].siz=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz+1;}
inline void pd(int u)
{
swap(e[u].ch[0],e[u].ch[1]);
lazy[e[u].ch[0]]^=1;
lazy[e[u].ch[1]]^=1;
lazy[u]^=1;
}
inline void spin(int u)
{
int fa=e[u].f,s=isr(u);
e[u].f=e[fa].f;
if(e[fa].f) e[e[fa].f].ch[isr(fa)]=u;
e[fa].ch[s]=e[u].ch[s^1];
e[fa].f=u;
if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;
e[u].ch[s^1]=fa;
up(fa);up(u);
}
void splay(int u,int fa=0)
{
while(e[u].f!=fa)
{
if(e[e[u].f].f&&lazy[e[e[u].f].f]) pd(e[e[u].f].f);
if(lazy[e[u].f]) pd(e[u].f);
if(lazy[u]) pd(u);
if(e[e[u].f].f==fa) spin(u);
else if(isr(u)^isr(e[u].f)) spin(u),spin(u);
else spin(e[u].f),spin(u);
}
if(!fa) root=u;
}
/*void insert(int& u,int v,int fa)
{
if(!u) {e[u=++siz].v=v;e[u].f=fa;splay(u);}
else if(e[u].v>v) insert(e[u].ch[0],v,u);
else insert(e[u].ch[1],v,u);
}*/
int kth(int u,int k)
{
if(lazy[u]) pd(u);
if(k==e[e[u].ch[0]].siz+1) {/*splay(u);*/return u;}
else if(k>e[e[u].ch[0]].siz+1) return kth(e[u].ch[1],k-e[e[u].ch[0]].siz-1);
return kth(e[u].ch[0],k);
}
void change(int l,int r)
{
int L=kth(root,l),R=kth(root,r+2);
splay(L);
splay(R,root);
lazy[e[e[root].ch[1]].ch[0]]^=1;
}
void build(int& u,int l,int r,int fa)
{
if(l>=r) return;
u=++siz;
int mid=(l+r)>>1;
e[u].v=mid;
e[u].siz=1;
e[u].f=fa;
if(l+1<r)
{
build(e[u].ch[0],l,mid,u);
build(e[u].ch[1],mid+1,r,u);
e[u].siz+=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz;
}
}
void print(int u)
{
if(u)
{
if(lazy[u]) pd(u);
print(e[u].ch[0]);
if(e[u].v>=1&&e[u].v<=N) printf("%d ",e[u].v);
print(e[u].ch[1]);
}
}
int main()
{
N=read();
M=read();
int a,b;
build(root,0,N+2,0);
while(M--)
{
a=read();
b=read();
if(a==b) continue;
change(a,b);
/*print(root);
cout<<endl;*/
}
print(root);
cout<<endl;
//system("pause >nul");
return 0;
}
轉載于:https://www.cnblogs.com/Mychael/p/8282901.html
![goalng nil interface淺析持續學習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)