講解博客：https://www.luogu.com.cn/blog/user19027/solution-p3369

模板博客：https://blog.csdn.net/clove_unique/article/details/50630280

單旋和雙旋的代碼都存了一份，雖然碼風不太一樣，但是都是可以過題的，大多數情況下雙旋的效率是高于單旋的，而有些奇怪的題目會卡雙旋，如果雙旋被卡了再換成單旋試試

代碼：

雙旋：

class Splay//存儲規則：小左大右，重復節點記錄 {#define root e[0].ch[1] //該樹的根節點private:class node{public:int v,father;//節點值，父級節點 int ch[2];//左孩子=0，右孩子=1int sum;//自己+自己下級有多少節點。在根節點為1。int recy;//記錄自己被重復了幾次};node e[N];//Splay樹主體int n,points;//使用存儲數,元素數void update(int x){e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].recy;}int identify(int x){return e[e[x].father].ch[0]==x?0:1;}void connect(int x,int f,int son)//連接函數。用法：connect(son,father,1/0){e[x].father=f;e[f].ch[son]=x;}//作用：使得x的father=f，f的son=x.void rotate(int x){int y=e[x].father;int mroot=e[y].father;int mrootson=identify(y);int yson=identify(x);int B=e[x].ch[yson^1];connect(B,y,yson);connect(y,x,(yson^1));connect(x,mroot,mrootson);update(y);update(x);}void splay(int at,int to)//將at位置的節點移動到to位置{to=e[to].father;while(e[at].father!=to){int up=e[at].father;if(e[up].father==to) rotate(at);else if(identify(up)==identify(at)){rotate(up);rotate(at);}else{rotate(at);rotate(at);}}}int crepoint(int v,int father){n++;e[n].v=v;e[n].father=father;e[n].sum=e[n].recy=1;e[n].ch[0]=e[n].ch[1]=0;return n;}void destroy(int x)//pop后摧毀節點 {e[x].v=e[x].ch[0]=e[x].ch[1]=e[x].sum=e[x].father=e[x].recy=0;if(x==n) n--;//最大限度優化}public:void init(){points=n=root=0;e[root].v=e[root].father=e[root].sum=e[root].recy=e[root].ch[0]=e[root].ch[1]=0;}int getroot(){return root;}int find(int v)//用于外部的find調用{int now=root;while(true){if(e[now].v==v){splay(now,root);return now;}int next=v<e[now].v?0:1;if(!e[now].ch[next]) return 0;now=e[now].ch[next];}}int build(int v)//內部調用的插入函數，沒有splay {points++;if(points==1)//特判無點狀態 {root=n+1;crepoint(v,0);}else{int now=root;while(true)//向下找到一個空節點 {e[now].sum++;//自己的下級肯定增加了一個節點 if(v==e[now].v){e[now].recy++;return now;}int next=v<e[now].v?0:1;if(!e[now].ch[next]){crepoint(v,now);e[now].ch[next]=n;return n;}now=e[now].ch[next];}}return 0;}void push(int v)//插入元素時，先添加節點，再進行伸展 {int add=build(v);splay(add,root);}void pop(int v)//刪除節點 {int deal=find(v);if(!deal) return;points--;if(e[deal].recy>1){e[deal].recy--;e[deal].sum--;return;}if(!e[deal].ch[0]){root=e[deal].ch[1];e[root].father=0;}else{int lef=e[deal].ch[0];while(e[lef].ch[1]) lef=e[lef].ch[1];splay(lef,e[deal].ch[0]);int rig=e[deal].ch[1];connect(rig,lef,1);connect(lef,0,1);update(lef);}destroy(deal);}int rank(int v)//獲取值為v的元素在這棵樹里是第幾小 {int ans=0,now=root;while(true){if(e[now].v==v) {ans+=e[e[now].ch[0]].sum;splay(now,root);return ans+1;}if(now==0) return 0;if(v<e[now].v) now=e[now].ch[0];else{ans=ans+e[e[now].ch[0]].sum+e[now].recy;now=e[now].ch[1];}}return 0;}int atrank(int x)//獲取第x小的元素的值 {if(x>points) return -inf;int now=root;while(true){int minused=e[now].sum-e[e[now].ch[1]].sum;if(x>e[e[now].ch[0]].sum&&x<=minused) break;if(x<minused) now=e[now].ch[0];else{x=x-minused;now=e[now].ch[1];}}splay(now,root);return e[now].v;}int upper(int v)//尋找該值對應的一個最近的上界值 {int now=root;int result=inf;while(now){if(e[now].v>=v&&e[now].v<result) result=e[now].v;if(v<e[now].v) now=e[now].ch[0];else now=e[now].ch[1];}return result;}int lower(int v)//尋找該值對應的一個最近的下界值 {int now=root;int result=-inf;while(now){if(e[now].v<=v&&e[now].v>result) result=e[now].v;if(v>e[now].v) now=e[now].ch[1];else now=e[now].ch[0];}return result;}#undef root }tree;

單旋：

補充一句：找前驅和后驅時pre和next函數只能找嚴格大于或小于的值，如果要找大于等于或小于等于的值，可以根據cnt另寫一個函數，并且在pre和next之前需要insert一下，將需要查詢的點旋轉到根節點上

class Splay {public:int ch[N][2],f[N],size[N],cnt[N],key[N];//size:子樹大小,cnt:當前節點出現次數,key:權值 int sz,root;inline void clear(int x){ch[x][0]=ch[x][1]=f[x]=size[x]=cnt[x]=key[x]=0;}inline bool get(int x){return ch[f[x]][1]==x;}inline void update(int x){if(x){size[x]=cnt[x];if(ch[x][0]) size[x]+=size[ch[x][0]];if(ch[x][1]) size[x]+=size[ch[x][1]];}}inline void rotate(int x){int old=f[x],oldf=f[old],whichx=get(x);ch[old][whichx]=ch[x][whichx^1]; f[ch[old][whichx]]=old;ch[x][whichx^1]=old; f[old]=x;f[x]=oldf;if(oldf)ch[oldf][ch[oldf][1]==old]=x;update(old); update(x);}inline void splay(int x){for(int fa;fa=f[x];rotate(x))if(f[fa])rotate((get(x)==get(fa))?fa:x);root=x;}inline void insert(int x){if(root==0){sz++; ch[sz][0]=ch[sz][1]=f[sz]=0; root=sz; size[sz]=cnt[sz]=1; key[sz]=x; return;}int now=root,fa=0;while(1){if(x==key[now]){cnt[now]++; update(now); update(fa); splay(now); break;}fa=now;now=ch[now][key[now]<x];if(now==0){sz++;ch[sz][0]=ch[sz][1]=0;f[sz]=fa;size[sz]=cnt[sz]=1;ch[fa][key[fa]<x]=sz;key[sz]=x;update(fa);splay(sz);break;}}}inline int find(int x)//查詢x的排名{int now=root,ans=0;while(1){if(x<key[now])now=ch[now][0];else{ans+=(ch[now][0]?size[ch[now][0]]:0);if(x==key[now]){splay(now); return ans+1;}ans+=cnt[now];now=ch[now][1];}}}inline int findx(int x)//找到排名為x的點{int now=root;while(1){if(ch[now][0]&&x<=size[ch[now][0]])now=ch[now][0];else{int temp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now];if(x<=temp) return key[now];x-=temp; now=ch[now][1];}}}inline int pre()//小于某個數的最大值 {int now=ch[root][0];while(ch[now][1]) now=ch[now][1];return now;}inline int next()//大于某個數的最小值 {int now=ch[root][1];while(ch[now][0]) now=ch[now][0];return now;}inline void del(int x){int whatever=find(x);if(cnt[root]>1){cnt[root]--; update(root); return;}if(!ch[root][0]&&!ch[root][1]) {clear(root); root=0; return;}if(!ch[root][0]){int oldroot=root; root=ch[root][1]; f[root]=0; clear(oldroot); return;}else if(!ch[root][1]){int oldroot=root; root=ch[root][0]; f[root]=0; clear(oldroot); return;}int leftbig=pre(),oldroot=root;splay(leftbig);ch[root][1]=ch[oldroot][1];f[ch[oldroot][1]]=root;clear(oldroot);update(root); } }tree;

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的(转)Splay伸展树模板的全部內容，希望文章能夠幫你解決所遇到的問題。

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