2019/7/16更新：封裝SplayTree進入class：例題：http://poj.org/problem?id=3622

一個伸展樹的板子：

#include<stdio.h> #include<math.h> #include<string.h> #include<stdlib.h> #include<time.h> // srand(unsigned)time(NULL));rand();#include<map> #include<set> #include<deque> #include<queue> #include<stack> #include<string> #include<fstream> #include<iostream> #include<algorithm>#define ll long long #define Pair pair<int,int> #define clean(a,b) memset(a,b,sizeof(a)) using namespace std;const int MAXN=1e5+10; const int INF32=0x3f3f3f3f; const ll INF64=0x3f3f3f3f3f3f3f3f; const ll MOD=1e9+7; const double PI=acos(-1.0); const double EPS=1.0e-8; //unsigned register // ios::sync_with_stdio(false)class SplayTree{struct Node{ll A,B;int l,r,f,siz;Node(ll _A=0,ll _B=0,int _l=0,int _r=0,int _f=0,int _siz=0){A=_A;B=_B;l=_l;r=_r;f=_f;siz=_siz;}friend int operator < (Node a,Node b){if(a.A==b.A) return a.B<b.B;return a.A<b.A;}};Node Tree[MAXN];int Lazy[MAXN];int Rt,Ecnt;//Rt的父節點是0,第一個節點從1開始。 void PushUp(int x){//次序 Tree[x].siz=Tree[Tree[x].l].siz+Tree[Tree[x].r].siz+1;}void PushDown(int x){//反轉 if(Lazy[x]){int temp=Tree[x].l;Tree[x].l=Tree[x].r;Tree[x].r=temp;Lazy[Tree[x].l]^=1;Lazy[Tree[x].r]^=1;Lazy[x]=0;}}void Rotate(int x,int oper){int y=Tree[x].f;PushDown(y);PushDown(x);if(oper){Tree[y].r=Tree[x].l;if(Tree[x].l!=0) Tree[Tree[x].l].f=y;Tree[x].l=y;}else{Tree[y].l=Tree[x].r;if(Tree[x].r!=0) Tree[Tree[x].r].f=y;Tree[x].r=y;}Tree[x].f=Tree[y].f;if(Tree[y].f){if(y==Tree[Tree[y].f].l) Tree[Tree[y].f].l=x;else Tree[Tree[y].f].r=x;}Tree[y].f=x;PushUp(y);}void Splay(int x,int f){PushDown(x);int y=Tree[x].f,z=0;while(y!=f){z=Tree[y].f;PushDown(z);PushDown(y);PushDown(x);if(z==f) Rotate(x,x==Tree[y].r);else{if((x==Tree[y].l^y==Tree[z].l)==0){Rotate(y,y==Tree[z].r);Rotate(x,x==Tree[y].r);}else{Rotate(x,x==Tree[y].r);Rotate(x,x==Tree[z].r);}}PushUp(x);y=Tree[x].f;}PushUp(x);if(f==0) Rt=x;}int MinNode(ll Key){int x=Rt,ans=-1;PushDown(x);while(1){if(Tree[x].A>=Key){//該節點可以取得 ans=x;if(Tree[x].l) x=Tree[x].l;//向左子節點 else return ans;}else{//不可以取得 if(Tree[x].r) x=Tree[x].r;//可以的話直接向右走了 else return ans;//沒有符合要求的 }}}int GetPre(){int x=Rt;if(Tree[x].l) x=Tree[x].l;else return x;while(1){if(Tree[x].r) x=Tree[x].r;else return x;}}public:void Intt(){clean(Lazy,0);Rt=0;Ecnt=0;}void Insert(ll A,ll B){Tree[++Ecnt]=Node(A,B,0,0,0,1);int y=0,x=Rt;while(x){y=x;if(Tree[Ecnt]<Tree[x]) x=Tree[x].l;else if(Tree[x]<Tree[Ecnt]) x=Tree[x].r;else return ;}if(y==0) Rt=Ecnt;else if(Tree[Ecnt]<Tree[y]){Tree[y].l=Ecnt;Tree[Ecnt].f=y;}else{Tree[y].r=Ecnt;Tree[Ecnt].f=y;}Splay(Ecnt,0);}ll DeleteMin(ll Key){//所有的B都符合要求，找到最小的A>=P int Pos=MinNode(Key);if(Pos==-1) return -1;ll Ans=Tree[Pos].A;Splay(Pos,0);//cout<<"Pos,Pre:"<<Pos<<" "<<GetPre()<<endl;Splay(GetPre(),0);//cout<<"Debug:\n";Show(Rt);cout<<"End\n";if(Pos==GetPre()){Rt=Tree[Rt].r;Tree[Rt].f=0;}else{Splay(Pos,Rt);Tree[Rt].r=Tree[Pos].r;Tree[Tree[Rt].r].f=Rt; }return Ans;}//-------int GetRt(){return Rt;}void Show(int x){if(x==0) return ;PushDown(x);printf("x:%d xf:%d xl:%d xr:%d (A,B)(%lld,%lld)\n",x,Tree[x].f,Tree[x].l,Tree[x].r,Tree[x].A,Tree[x].B);Show(Tree[x].l); // printf("A:%lld B:%lld\n",Tree[x].A,Tree[x].B);Show(Tree[x].r);} }; struct Node{ll P,G;Node(ll _P=0,ll _G=0){P=_P;G=_G;}friend int operator < (Node a,Node b){if(a.G==b.G) return a.P<b.P;return a.G<b.G;} }; SplayTree Spl; Node Cows[MAXN],Goods[MAXN]; int n,m;int PosX(ll Key,int l,int r){while(l<=r){int mid=(l+r)>>1;if(Goods[mid].G<Key) l=mid+1;else r=mid-1;}return l; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) scanf("%lld%lld",&Cows[i].P,&Cows[i].G);for(int i=1;i<=m;++i) scanf("%lld%lld",&Goods[i].P,&Goods[i].G);sort(Cows+1,Cows+1+n);sort(Goods+1,Goods+1+m);ll ans=0;int flag=1,tmp=m;Spl.Intt();for(int i=n;i>=1;--i){int Pos=PosX(Cows[i].G,1,tmp);for(int j=Pos;j<=tmp;++j) Spl.Insert(Goods[j].P,Goods[j].G);ll temp=Spl.DeleteMin(Cows[i].P);if(temp==-1){//找最小的花費 flag=0;break;}ans+=temp;tmp=Pos-1;}if(flag==0) printf("-1\n");else printf("%lld\n",ans); }

在開頭寫下伸展樹的應用情況，以及使用方法，由于本人是個蒟蒻，因此總結不為全面，有更多的方法希望指出和提醒：

對于伸展樹的一些應用：
因為伸展樹和核心是 旋轉節點 ，所以我們就從旋轉節點處開始入手，進行一些 騷操作。?
1.裸的伸展樹，實現增刪改查，對節點的直接操作，比較簡單，會板子就行

2.對區間的修改，例：對區間[a,b]修改，
可以將節點a-1旋轉到根節點的位置，將b+1旋轉到根節點的右子節點，
這樣的話，根節點的右子節點的左子樹就是區間[a,b];
我們可以直接對于每個節點里面儲存的信息進行修改
(節點中可以儲存以該節點為根節點的一些信息，修改也好修改，旋轉向下傳遞)?

3.在a后面插入一些數，那么我們先把插入的這些數建成一顆伸展樹，
用分治法建立一顆完全平衡的二叉樹，
就是說每次把最中間的節點轉到根節點的右邊，?
最后將這顆新的子樹掛到 根右子節點的左子節點上?

4.刪除一個區間[a,b]內的數 ，可以參考第二種情況，
旋轉，然后直接刪除一個一顆子樹，繼續維護伸展樹?

5.區間的翻轉，對區間[a,b]的翻轉，可以引用一個lazy數組進行標記，每次旋轉的時候判斷一下，翻轉則翻轉左右子節點，然后向下推一個節點，然后刷新本節點lazy數組。

?

/*-----------------------伸展樹----------------------------*/ 伸展數(Splay Tree)，又叫分裂樹，是一種二叉排序樹，能在O(log n)內完成插入，查找，刪除操作； 伸展樹上的一般操作都基于伸展操作： 假設要對一個二叉查找樹執行一系列查找操作，為使整個查找時間更小，被查效率高的那些條目應當經常處于靠近樹根的位置； 于是想設計一個簡單方法，在每次查找之后對樹進行重構，把被查找的條目搬移到離樹根近一些的地方。 伸展樹是一種自調形式的二叉查找樹，他會沿著從某個節點到樹根之間的路徑，通過一系列旋轉的把這個節點搬移到樹根去。 它的優勢在于不需要記錄用于平衡樹的冗余信息。關鍵詞： 二叉排序樹 平衡樹 因此我決定先學這兩個數據結構： //--------------------二叉排序樹： 又稱 二叉查找樹||二叉搜索樹 定義： 二叉排序樹或者一顆空樹，或者具有下列性質的二叉樹： 1.若左子樹不空，則左子樹上所有節點的值均小于它的根節點的值； 2.若右子樹不空則右子樹上所有節點的值均大于它的根節點的值； 3.左右子樹分別為二叉排序樹； 4.沒有 鍵值 相等的節點 //鍵值(key)： //鍵值是 window 中注冊表中的概念。鍵值位于注冊表結構鏈末端，和文件系統的文件類似； //鍵值包含集中數據類型，以適應不同環境的使用需求。 // 注冊表中，是通過鍵和子鍵來管理各種信息； 簡單的說 二叉排序樹就是一棵從左往右越來越大的樹。 //---查找： 若根節點的關鍵字等于查找的關鍵字，成功 否則，判斷查找關鍵字值，遞歸進入左子樹或右子樹 子樹為空，查找不成功 //---插入刪除： 二叉排序樹是一種動態樹表，其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值時在進行插入。 新插入的節點一定是一個新添加的葉子節點而且查找不成功時查找路徑上訪問的最后一個節點的左||右子節點 插入算法： 首先執行查找算法，找出被插節點的父節點； 判斷被插節點是其父節點的左||右子節點，被插節點作為子節點插入。 若二叉樹為空，則首先單獨生成根節點。 新插入的節點總是葉子節點。 struct bitree{int data;bitree *lchild,*rchild; }; //在二叉排序樹中插入查找關鍵字key bitree* insertbst(bitree *t,int key) {if(t==NULL){t=new bitree();t->lchild=t->rchild=NULL;t->data=key;return t;}if(key<t->data)t->lchild=insertbst(t->lchild,key);elset->rchild=insertbst(t->rchild,key);return t; } //n個數據在數組d中，tree為二叉排序樹 樹根 bitree* create_bitree(bitree *tree,int d[],int n) {for(int i=0;i<n;++i)tree=insertbst(tree,d[i]); }//---刪除節點 在二叉排序樹中刪除一個節點，分成三種情況： 1.若*p節點為葉子節點，即PL(左子樹)和PR(右子樹)均為空樹，由于刪去葉子節點不破壞整棵樹的結構，則可以直接刪除此子節點。 2.若*p節點只有左子樹PL或右子樹PR，此時只要令PL||PR直接成為其雙親節點*f的左子樹(當*p是左子樹)或右子樹(當*p是右子樹) ，此時也不破壞二叉排序樹的特性 3. 若*p節點的左子樹和右子樹均不為空 。在刪去*p后，為保持其他元素的相對位置不變，課按中序遍歷保持有序進行調整。 有兩種做法： 一：令*p左子樹為*f的左||右子樹(依照*p是*f左子樹還是右子樹而定)，*s為*p左子樹的最右下的節點，而*p的右子樹為*s的右子樹； 二：令*p的直接前驅(或直接后繼)替代*p，然后再從二叉排序樹中刪去他的直接前驅(直接后繼) --即讓*f的左子樹(如果有的話)成為*p左子樹的最坐下節點(如果有的話)，再讓*f成為*p的左右節點的父節點。 直白的說就是：因為二叉查找樹的原因，被刪節點*p左子樹的最右邊的節點的值必定小于*p右子樹根節點的值 ， 因此可以直接把*p的右子樹拼接到*p左子樹的最右邊的子節點上 算法如下：bool Delete(bitree*); bool Deletebst(bitree &tparent,bitree &T,keytype key) {//若二叉排序樹T中存在關鍵字等于key的數據元素時，則刪除該數據元素，并返回true否則返回false if(!T)return false;else{if(key==T->data.key)//找到關鍵字等于key的數據元素 return Delete(parent_t,t);else if(key<T->lchild.key)return Deletebst(T,T->lchild,key);elsereturn Deletebst(T,T->rchild,key);}return true; }bool Delete(bitree &fp,bitree &p) {//從二叉排序樹中刪除節點p，并重接它的左||右子樹 if(!p->rchild)//只需要連接一棵樹即可 {fp->lchild=p->lchild;delete(p);}else if(!p->lchild){fp->rchild=p->rchild;delete(p);}else//連接兩棵樹 {q=p;fp->lchild=p->lchild;s=p->lchild;//轉左 while(s->rchild)//向右到盡頭 {q=s;s=s->rchild;}//此時q是s的父節點 s->rchild=p->rchild;//將s的左子樹作為q的右子樹 delete(p);}return true; }//----------------平衡樹 平衡二叉樹(Balanced Binary Tree)具有以下性質: 它是一顆空樹||它的左右兩個子樹高度差的絕對值不超過1，并且左右兩個子樹都是一顆平衡二叉樹。 平衡樹的實現方法有： 紅黑樹，AVL，替罪羊樹，Treap，伸展樹等 最小平衡二叉樹節點的公式：F(n)=F(n-1)/*左子樹樹節點數量*/+F(n-2)/*右子樹節點數量*/+1; 平衡樹的維持方法： 二叉左旋： //待學習。。。 二叉右旋： //待學習。。。 //---------------------------了解完基礎知識，開始學習伸展樹-------- 如何構造一個伸展樹： //---方法一： 訪問到X節點時，從X處單旋轉將X移動到根節點處， 也就是將訪問路徑上的每個節點和他們的父節點都實施旋轉 。 這種旋轉的效果是將訪問節點X一直推向樹根， 但是不好的地方是可能將其他節點推向更深的位置， 這種效果并不好，因為它沒有改變訪問路徑上其他節點的后序訪問狀況。//---方法二： 和方法一類似， 在訪問到節點X時，根據X節點和其父節點(P)以及祖父節點(G)之間的形狀做相應的單選轉或雙旋轉。 如果三個節點構成LR或RL時(即之字型)，則進行相應的雙旋轉； 如果構成LL或者RR時進行對應的單選轉(一字型)。 這樣展開的效果是將X推向根節點的同時， 訪問路徑上其他節點的深度大致都減少了一半 (某些淺的節點最多向后退后了兩層)。 這樣做對絕大多數訪問路徑上的節點的后續訪問都是有益的。//-----伸展樹的基本特性： 當訪問路徑太長而導致超出正常查找時間的時候，這些旋轉將對未來的操作(下一次訪問)有益； 當訪問耗時很少的時候，這些旋轉則不那么有益甚至有害。 /*--一個（舍棄）的 解釋 //------伸展樹的基本操作 伸展樹的伸展方式有兩種，一種是自下向上的伸展；另一種是自上向下的伸展。 比較容易理解的是自下向上的伸展，我們會重點解釋自頂向下的實現方式。 //---自下向上 先自上向下搜尋X節點， 當搜索到X節點時，從X節點開始到根節點的路徑上所有的節點進行旋轉 ， 最終將X節點推向根節點，將訪問路徑上的大部分節點的深度都降低。具體旋轉需根據不同的情形進行，在X節點處有三種情形需要考慮 （假設X的父節點是P，X的祖父節點為G）： 1.X的父節點P就是樹根的情形，這種情形比較簡單，只需要將X和P進行旋轉即可， X和P構成LL就是左單選轉，構成RR就右單旋轉 2.X和P和G之間構成"之"字型的情形，即LR||RL類型。 如果是LR則進行左雙旋轉，如果是RL進行右雙旋轉 。 3.X和P和G之間構成"一"字形的情形，即RR||LL類型； 如果LL則執行兩次單左旋轉，如果是RR則執行兩次單右旋轉；代碼先不寫了：效率據說不高 //--自頂向下的伸展*/

自頂向下的伸展：

換成圖片就是這樣：

然后是運行的代碼：

#include<stdio.h> #include<stdlib.h> #include<iostream> using namespace std;struct splaytree_node{int key;splaytree_node *left,*right; };splaytree_node *splaytree_search(splaytree_node *x,int key)//遞歸查找 {if(x==NULL||x->key==key)return x;if(key<x->key)return splaytree_search(x->left,key);elsereturn splaytree_search(x->right,key); }splaytree_node *splaytree_splay(splaytree_node *tree,int key)//旋轉 {splaytree_node N,*l,*r,*c;if(tree==NULL)return tree;N.left=N.right=NULL;l=r=&N;while(1)//開始旋轉調整 {//cout<<tree->key<<endl;if(key<tree->key)//向l方向調整 {if(tree->left==NULL)//左邊沒東西了 break;if(key<tree->left->key)//左邊仍有值 && key仍小于 {c=tree->left;tree->left=c->right;c->right=tree;tree=c;//現在已經調整過節點 向左旋轉一個節點 if(tree->left==NULL)break;//如果左邊沒有值了，就結束循環 }r->left=tree;r=tree;tree=tree->left;}else if(key>tree->key)//向r方向調整 {if(tree->right==NULL)break;if(key>tree->right->key){c=tree->right;tree->right=c->left;c->left=tree;tree=c;if(tree->right=NULL)break;}l->right=tree;l=tree;tree=tree->right;}else// 已經是該節點了{break;}}//當親位置 tree為目標點||最接近目標點 // cout<<tree<<" "<<tree->key<<" "<<tree->left<<" "<<tree->right<<endl;l->right=tree->left;r->left=tree->right;tree->left=N.right;tree->right=N.left; // cout<<tree<<" "<<tree->key<<" "<<tree->left<<" "<<tree->right<<endl;//翻上去 return tree; }splaytree_node *creat_splaytree_node(int key,splaytree_node *left,splaytree_node*right) {splaytree_node *p;if((p=(splaytree_node*)malloc(sizeof(splaytree_node)))==NULL)return NULL;p->key=key;p->left=left;p->right=right;return p; }splaytree_node *insert_node(splaytree_node* tree,splaytree_node *z) {splaytree_node *y=NULL;//要插入的目標位置的上一個位置 splaytree_node *x=tree;//要插入的目標位置 while(x!=NULL){y=x;if(z->key<x->key)x=x->left;else if(z->key>x->key)x=x->right;else{cout<<"Error：此節點已存在！"<<endl;free(z);return tree;}}if(y==NULL)//此時是一顆空樹，直接返回z即可 tree=z;else if(z->key<y->key)//y的左節點 y->left=z;elsey->right=z;//y的右節點 return tree; }splaytree_node *splaytree_insert(splaytree_node *tree,int key)//插入 {//cout<<tree<<" "<<key<<endl;splaytree_node *z;z=creat_splaytree_node(key,NULL,NULL);//cout<<z<<" "<<z->key<<" "<<key<<endl;if(z==NULL)//創建失敗 return tree;tree=insert_node(tree,z);//插入節點 //cout<<tree->key<<" "<<tree<<endl; tree=splaytree_splay(tree,key);//旋轉節點(維護該樹) return tree; }splaytree_node *splaytree_delete(splaytree_node *tree,int key)//刪除 {splaytree_node *x;if(tree==NULL)return NULL;if(splaytree_search(tree,key)==NULL)return tree;//沒有找到tree=splaytree_splay(tree,key);//旋轉為根節點if(tree->left!=NULL){x=splaytree_splay(tree->left,key);//將根節點左子樹最大的節點旋轉為根節點 x->right=tree->right;}elsex=tree->right;free(tree);return x; }void print_splaytree(splaytree_node *tree,int key,int direction)//打印樹 {if(tree!=NULL){if(direction==0)cout<<tree->key<<" is root"<<endl;elsecout<<tree->key<<" is "<<key<<" 's "<<direction<<" child"<<endl;print_splaytree(tree->left,tree->key,-1);print_splaytree(tree->right,tree->key,1);} } /* 10 1 2 3 4 5 6 7 8 9 10 7 */ int main() {//插入 int n;cin>>n;splaytree_node *root=NULL;int data;for(int i=1;i<=n;++i){cin>>data;root=splaytree_insert(root,data);//cout<<root<<endl;print_splaytree(root,root->key,0);}cout<<"delete a node"<<endl;cin>>data;root=splaytree_delete(root,data);print_splaytree(root,root->key,0); }

由于自頂向下伸展會導致，節點刷新的時候需要重新刷新，因此，在比較自下至上伸展之后，發現自下向上伸展對節點的維護更加方便，因此，下面學習伸展樹的自下向上的伸展：

?

其實自下而上的伸展和自上而下的類似，直接上板子了：

//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<math.h> //#include<map> //#include<set> #include<deque> #include<queue> #include<stack> #include<bitset> #include<string> #include<fstream> #include<iostream> #include<algorithm> using namespace std; #define ll long long //#define max(a,b) (a)>(b)?(a):(b) //#define min(a,b) (a)<(b)?(a):(b) #define clean(a,b) memset(a,b,sizeof(a))// 水印 //std::ios::sync_with_stdio(false); const int MAXN=2e5+10; const int INF=0x3f3f3f3f; const ll mod=1e9+7;struct node{int id,data,maxval;node *l,*r,*f;/*使用從下到上的伸展方式，多了一個f指針記錄父節點的位置找到要旋轉的目標點，旋轉目標點，直到目標點的父節點是目標父節點*/ }; node *root;void show(node *x) {if(x==NULL)return;cout<<x<<" : "<<x->id<<" "<<x->data<<" "<<x->l<<" "<<x->r<<endl;show(x->l);show(x->r); }void rotate(node *x,bool oper) {node *y=x->f;if(y==NULL)return ;if(oper){y->r=x->l;if(x->l!=NULL)x->l->f=y;x->l=y;}else{y->l=x->r;if(x->r!=NULL)x->r->f=y;x->r=y;}x->f=y->f;if(y->f!=NULL){if(y==y->f->l)y->f->l=x;elsey->f->r=x;}y->f=x;if(y==root)root=x;updata(y);updata(x); }void splay(node *x,node *f) {node *y=x->f,*z=NULL;while(y!=f){z=y->f;if(z==f){rotate(x,x==y->r);}else{if((x==y->l ^ y==z->l)==0)//一字型 {rotate(y,y==z->r);rotate(x,x==y->r);}else//之字型 {rotate(x,x==y->r);rotate(x,x==z->r);}}y=x->f;}}void insert(int id,int data) {node *z;z=(node*)malloc(sizeof(node));if(z==NULL)return ;z->data=data;z->id=id;z->maxval=data;z->l=z->r=z->f=NULL;node *y=NULL;node *x=root;while(x!=NULL){y=x;if(z->id<x->id)x=x->l;else if(z->id>x->id)x=x->r;elsereturn ;}if(y==NULL)root=z;else if(z->id<y->id){y->l=z;z->f=y;}else{z->f=y;y->r=z;}splay(z,NULL); }void delete_node(node *x) {if(x==NULL)return ;delete_node(x->l);delete_node(x->r);free(x); }int main() {std::ios::sync_with_stdio(false);int n;while(cin>>n){root=NULL;//每次重置根節點 int data;insert(0,0);//插入0個 for(int i=1;i<=n;++i)//按照下標建樹 {cin>>data;insert(i,data);}insert(n+1,0);//插入n+1個，防止邊界 show(root);delete_node(root);//注意最后的時候一定要釋放空間，否則會MLE } }

下面是一個用數組模擬的板子，以后就不用每次都delete了：

就以HDU-3487為例子寫的一個板子：

//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h>//#include<map> //#include<set> #include<deque> #include<queue> #include<stack> #include<bitset> #include<string> #include<fstream> #include<iostream> #include<algorithm> using namespace std; #define key_val son[son[root][1]][0] //根節點 的 右子節點 的 左子節點 typedef long long ll; const int N = 300010, INF = 0x3f3f3f3f, MOD = 1000000; //此時記錄遍歷數據不已固定的id記錄數據了，我們用該節點前面有多少節點個個數作為id，時刻刷新id，實現動態可變 int son[N][2], fat[N], siz[N]/*該子樹的節點個數包括自身*/; int key[N]/*節點權值*/, /*val[N],*/ lazy[N];//隋標記 int root, tot, cnt; int arr[N]; int n, m; void new_node(int val, int fa, int &x) {x = ++tot;fat[x] = fa, key[x] = val;siz[x] = 1, lazy[x] = 0;son[x][0] = son[x][1] = 0; } void push_up(int x)//該節點的節點個數等于左右子樹的節點個數+1 {// push_up的操作就是刷新 x子樹的節點個數 siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1; } void push_down(int x) {// push_down的操作就是刷新該節點是否需要反轉 if(lazy[x])//該節點的lazy存在 {swap(son[x][0], son[x][1]);//交換該節點的左右子樹 區間反轉 lazy[son[x][0]] ^= 1, lazy[son[x][1]] ^= 1;// 左節點和右節點刷新 lazy[x] = 0;//該節點重置 } } void Rotate(int x, int p) {int y = fat[x];push_down(y); push_down(x);son[y][!p] = son[x][p], fat[son[x][p]] = y;if(fat[y]) son[fat[y]][son[fat[y]][1]==y] = x;fat[x] = fat[y];son[x][p] = y, fat[y] = x;push_up(y); } void splay(int x, int goal) {push_down(x);while(fat[x] != goal){int y = fat[x], z = fat[y];//在這里下傳翻轉標記，在rotate里下傳標記可能會使樹形改變導致旋轉出錯push_down(z); push_down(y); push_down(x);if(fat[y] == goal) Rotate(x, son[y][0] == x);else{int p = son[fat[y]][0] == y;if(son[y][p] == x) Rotate(x, !p), Rotate(x, p);else Rotate(y, p), Rotate(x, p);}}push_up(x);if(goal == 0) root = x;//刷新根節點 } //int get_prec(int x) //{ // push_down(x); // x = son[x][0]; // push_down(x); // while(son[x][1]) // x = son[x][1], push_down(x); // return x; //} int get_succ(int x)//x傳進來，輸出x節點的后繼 {push_down(x);x = son[x][1];//x的右子節點 push_down(x);while(son[x][0]) //一直向左找 x = son[x][0], push_down(x);return x; } int get_kth(int k)//找到目標元素所在的節點 {int x = root;//從根節點開始 push_down(x);//刷新該節點 while(true){//這里細數k和siz的作用：//因為旋轉過了，原來的id會混亂，因此此時對節點id的刷新 以該節點為子節點的個數多少為id// if(k <= siz[son[x][0]]) //k是該節點的 左子樹 x = son[x][0];else if(k > siz[son[x][0]] + 1) //k不是在該節點的左子樹和該節點處 k =k - (siz[son[x][0]] + 1), x = son[x][1];//刷新k，并且x右走 else break;// 找到該節點 push_down(x);}return x; } //int get_kth(int x, int k) //{ // push_down(x); // if(k <= siz[son[x][0]]) return get_kth(son[x][0], k); // else if(k > siz[son[x][0]] + 1) return get_kth(son[x][1], k - siz[son[x][0]] - 1); // return x; //} void build(int l, int r, int fa, int &x) {if(l > r) return;int mid = (l + r) >> 1;new_node(mid, fa, x);build(l, mid-1, x, son[x][0]);build(mid+1, r, x, son[x][1]);push_up(x); } void cut(int a, int b, int c)//a - b 加到c后面 {splay(get_kth(a), 0);//把第a位置的節點旋轉道根節點 splay(get_kth(b+2), root);//b旋轉到根節點的子節點 int tmp = son[son[root][1]][0];//根節點的右子節點的左子節點 son[son[root][1]][0] = 0;//節點變成0 ，此時已經把a~b區間移除 push_up(son[root][1]), push_up(root);//刷新根節點的右子節點和根節點 ，移除成功 splay(get_kth(c+1), 0);//旋轉c+1節點為跟節點 splay(get_succ(root), root);// 旋轉根節點的 后繼為子節點（清空根節點的右子節點的左子樹） son[son[root][1]][0] = tmp, fat[son[son[root][1]][0]] = son[root][1];//a - b 子樹掛上去 push_up(son[root][1]), push_up(root);//刷新節點 } void rev(int a, int b)//反轉a - b區間 {splay(get_kth(a), 0);//旋轉a到根節點 splay(get_kth(b+2), root);//旋轉b 到根節點的右子節點 lazy[son[son[root][1]][0]] ^= 1;//根節點的右子節點 的左子樹 隋標記 } void inorder(int x)//輸出序列 中序遍歷 {if(! x) return;//x子樹為空 push_down(x);//刷新x inorder(son[x][0]);//遞歸找左子節點 if(key[x] > 0) //當前節點 存在 printf("%d%c", key[x], ++cnt == n ? '\n' : ' ');//輸出該節點，并且判斷是否換行 inorder(son[x][1]);// 遞歸右子節點 } void init() {root = tot = 0;son[0][0] = son[0][1] = siz[0] = fat[0] = 0;key[0] = /*val[0] =*/ lazy[0] = 0;new_node(-INF, 0, root);//插入兩個邊界值，然后把序列插入兩個邊界值之間new_node(-INF, root, son[root][1]);build(1, n, son[root][1], son[son[root][1]][0]);//1~n push_up(son[root][1]), push_up(root); } int main() {char op[10];int a, b, c;while(scanf("%d%d", &n, &m), n != -1 || m != -1){init();for(int i = 1; i <= m; i++){scanf(" %s%d%d", op, &a, &b);if(op[0] == 'C'){scanf("%d", &c);cut(a, b, c);//a - b 區間加到c后面 }else rev(a, b);//反轉 a - b 區間 }cnt = 0;inorder(root);//輸出最終序列 }return 0; }

然后是我用子節的那個板子修改的結構體版，最后是格式錯誤，但是答案是對的，而且時間也差不多：

//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<math.h> //#include<map> //#include<set> #include<deque> #include<queue> #include<stack> #include<bitset> #include<string> #include<fstream> #include<iostream> #include<algorithm> using namespace std; #define ll long long //#define max(a,b) (a)>(b)?(a):(b) //#define min(a,b) (a)<(b)?(a):(b) #define clean(a,b) memset(a,b,sizeof(a))// 水印 //std::ios::sync_with_stdio(false); const int MAXN=3e5+10; const int INF=0x3f3f3f3f; const ll mod=1e9+7;struct node{int siz,val;int l,r,f; }tree[MAXN]; int root,ecnt; bool lazy[MAXN]; int n,m;void intt() {clean(tree,0);clean(lazy,0);root=0;ecnt=0; }void push_up(int x) {tree[x].siz=tree[tree[x].l].siz+tree[tree[x].r].siz+1;//cout<<tree[x].siz<<endl; }void push_down(int x) {if(lazy[x]){int temp=tree[x].l;tree[x].l=tree[x].r;tree[x].r=temp;lazy[tree[x].l]^=1;lazy[tree[x].r]^=1;lazy[x]=0;} }void rotate(int x,bool oper) {int y=tree[x].f;push_down(y);push_down(x);if(oper){tree[y].r=tree[x].l;if(tree[x].l!=0)tree[tree[x].l].f=y;tree[x].l=y;}else{tree[y].l=tree[x].r;if(tree[x].r!=0)tree[tree[x].r].f=y;tree[x].r=y;}tree[x].f=tree[y].f;if(tree[y].f){if(y==tree[tree[y].f].l)tree[tree[y].f].l=x;elsetree[tree[y].f].r=x;}tree[y].f=x; // if(y==root) // root=x;push_up(y); }void splay(int x,int f) {push_down(x);int y=tree[x].f,z=0;while(y!=f){z=tree[y].f;push_down(z);push_down(y);push_down(x);if(z==f)rotate(x,x==tree[y].r);else{if((x==tree[y].l ^ y==tree[z].l)==0){rotate(y,y==tree[z].r);rotate(x,x==tree[y].r);}else{rotate(x,x==tree[y].r);rotate(x,x==tree[z].r);}}push_up(x);y=tree[x].f;}push_up(x);if(f==0)root=x; }void insert(int val) {tree[++ecnt].val=val;tree[ecnt].siz=1;tree[ecnt].l=tree[ecnt].r=tree[ecnt].f=0;int y=0,x=root;while(x){y=x;if(tree[x].val>val)x=tree[x].l;else if(tree[x].val<val)x=tree[x].r;elsereturn ;}if(y==0)root=ecnt;else if(val<tree[y].val){tree[y].l=ecnt;tree[ecnt].f=y;}else{tree[y].r=ecnt;tree[ecnt].f=y;}splay(ecnt,0); }int get_next(int x) {push_down(x);x=tree[x].r;push_down(x);while(tree[x].l){x=tree[x].l;push_down(x);}return x; }int get_node(int k) {int x=root;push_down(x);while(1){//cout<<x<<" "<<tree[x].siz<<" "<<tree[x].val<<" "<<k<<endl;if(k<=tree[tree[x].l].siz)x=tree[x].l;else if(k>tree[tree[x].l].siz+1){k=k-(tree[tree[x].l].siz+1);x=tree[x].r;}elsebreak;push_down(x);}return x; }void cut(int a,int b,int c) {int str=get_node(a),ed=get_node(b+2);splay(str,0);splay(ed,root);int temp=tree[tree[root].r].l;tree[tree[root].r].l=0;push_up(tree[root].r);push_up(root);//------------int key=get_node(c+1);splay(key,0);int nex=get_next(root);splay(nex,root);tree[tree[root].r].l=temp;tree[tree[tree[root].r].l].f=tree[root].r;push_up(tree[root].r);push_up(root); } void show(int x) {if(x==0)return ;push_down(x);show(tree[x].l);if(tree[x].val>0&&tree[x].val<n+1)printf("%d ",tree[x].val);//cout<<tree[x].val<<" ";show(tree[x].r); } void rev(int a,int b) {int str=get_node(a);//cout<<tree[str].val<<endl;//cout<<tree[root].val<<endl;show(root);cout<<endl;splay(str,0);//cout<<tree[root].val<<endl;show(root);cout<<endl;//cout<<"get_ed"<<endl;int ed=get_node(b+2);//cout<<ed<<" "<<tree[ed].val<<endl;splay(ed,root);//cout<<tree[root].val<<endl;(root);cout<<endl;lazy[tree[tree[root].r].l] ^=1; }int main() {//std::ios::sync_with_stdio(false);while(~scanf("%d%d",&n,&m)){if(n==-1&&m==-1)break;intt();insert(0);for(int i=1;i<=n;++i)insert(i);insert(n+1);//show(root);cout<<endl;char oper[5];int a,b,c;while(m--){ // for(int i=0;i<=n+1;++i) // cout<<tree[i].siz<<" "; // cout<<endl;scanf("%s%d%d",&oper,&a,&b);if(oper[0]=='C'){scanf("%d",&c);cut(a,b,c);}elserev(a,b);//cout<<tree[root].val<<endl;show(root);cout<<endl;}show(root);printf("\n");} }/* 8 2 CUT 3 5 4 FLIP 2 6 -1 -1*/

然后是區間的增加和修改：

以POJ-3468為例（其實這道題用線段樹更好，伸展樹的話，時間用的會更加長）

ac：4800ms+

//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<math.h> //#include<map> //#include<set> #include<deque> #include<queue> #include<stack> #include<bitset> #include<string> #include<fstream> #include<iostream> #include<algorithm> using namespace std; #define ll long long //#define max(a,b) (a)>(b)?(a):(b) //#define min(a,b) (a)<(b)?(a):(b) #define clean(a,b) memset(a,b,sizeof(a))// 水印 //std::ios::sync_with_stdio(false); const int MAXN=1e5+10; const int INF=0x3f3f3f3f; const ll mod=1e9+7;struct node{ll val,id,sumval,size;int l,r,f; }tree[MAXN]; int root,ecnt; ll lazy[MAXN]; int n,m;void intt() {clean(tree,0);clean(lazy,0);root=ecnt=0; }void push_up(int x) {tree[x].sumval=tree[x].val;tree[x].sumval+=tree[tree[x].r].sumval+tree[tree[x].l].sumval;tree[x].size=tree[tree[x].l].size+tree[tree[x].r].size+1; }void push_down(int x) {if(lazy[x])//向下推值 {tree[x].val+=lazy[x];//刷新該值 tree[tree[x].l].sumval+=lazy[x]*tree[tree[x].l].size;//左子節點刷新 tree[tree[x].r].sumval+=lazy[x]*tree[tree[x].r].size;//右子節點刷新 lazy[tree[x].l]+=lazy[x];lazy[tree[x].r]+=lazy[x];lazy[x]=0; // cout<<"push_down:"; // cout<<tree[x].id<<" "<<tree[x].val<<" "<<tree[x].sumval<<endl;} } void show(int x) {if(x==1||x==0)return ;push_down(x);cout<<tree[x].val<<" ";//cout<<x<<": "<<tree[x].id<<" "<<tree[x].val<<endl;show(tree[x].l);show(tree[x].r); } void rotate(int x,bool oper) {int y=tree[x].f;push_down(x);push_down(y);if(oper){tree[y].r=tree[x].l;if(tree[x].l!=0)tree[tree[x].l].f=y;tree[x].l=y;}else{tree[y].l=tree[x].r;if(tree[x].r!=0)tree[tree[x].r].f=y;tree[x].r=y;}tree[x].f=tree[y].f;if(tree[y].f){if(y==tree[tree[y].f].l)tree[tree[y].f].l=x;elsetree[tree[y].f].r=x;}tree[y].f=x;push_up(y); }void splay(int x,int f) {push_down(x);int y=tree[x].f,z=0;while(y!=f){z=tree[y].f;push_down(z);push_down(y);push_down(x);if(z==f)rotate(x,x==tree[y].r);else{if((x==tree[y].l ^ y==tree[z].l)==0){rotate(y,y==tree[z].r);rotate(x,x==tree[y].r);}else{rotate(x,x==tree[y].r);rotate(x,x==tree[z].r);}}push_up(x);y=tree[x].f;}push_up(x);if(f==0)root=x;}void insert(int val,int id) {tree[++ecnt].val=val;tree[ecnt].sumval=val;tree[ecnt].id=id;tree[ecnt].size=1;tree[ecnt].l=tree[ecnt].r=tree[ecnt].f=0;int y=0,x=root;while(x){y=x;if(tree[x].id>id)x=tree[x].l;else if(tree[x].id<id)x=tree[x].r;elsereturn ;}if(y==0)root=ecnt;else if(id<tree[y].id){tree[y].l=ecnt;tree[ecnt].f=y;}else{tree[y].r=ecnt;tree[ecnt].f=y;}splay(ecnt,0); }int get_node(int id) {int x=root;push_down(x);while(1){if(tree[x].id<id)x=tree[x].r;else if(tree[x].id>id)x=tree[x].l;elsebreak;push_down(x);}return x; }ll Query(int a,int b)//查詢a~b {splay(get_node(a-1),0);splay(get_node(b+1),root);//旋轉 return tree[tree[tree[root].r].l].sumval; }void add(int a,int b,int x) {splay(get_node(a-1),0);splay(get_node(b+1),root);//旋轉 lazy[tree[tree[root].r].l]+=x;tree[tree[tree[root].r].l].sumval+=tree[tree[tree[root].r].l].size*x; }int main() {//std::ios::sync_with_stdio(false);while(~scanf("%d%d",&n,&m)){intt();ll data;insert(0,0);for(int i=1;i<=n;++i){scanf("%lld",&data);insert(data,i);}insert(0,n+1);//show(root);cout<<endl;//建樹完成 char ch[5];ll a,b,c;while(m--){scanf("%s",&ch);if(ch[0]=='Q'){scanf("%lld%lld",&a,&b);printf("%lld\n",Query(a,b));}else{scanf("%lld%lld%lld",&a,&b,&c);add(a,b,c);}//show(root);cout<<endl;}} }/*10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4*/

?

總結

以上是生活随笔為你收集整理的数据结构--伸展树(伸展树构建二叉搜索树)-学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。