splay：伸展樹
特點：滿足 左子樹所有值<父親<右子樹所有值
功能：自平衡樹，可插入，刪除，查詢x的排名，查詢排名為k的值，查詢x的前驅、後繼
複雜度：log(n)
旋轉操作：讓兒子與父親位置互換，但平衡樹的特性不改變，splay可以進行雙旋優化
以下代碼，查詢前驅和後繼的方法，先用插入一個x，rnk()函數把x旋轉到根節點，再用pre()或next()函數來獲取前驅或後繼。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=3e5+7; 4 5 int f[N],cnt[N],ch[N][2],key[N],size[N]; 6 // 父親 個數 孩子 節點值 子樹節點數量 7 int sz,rt; 8 9 void clear(int x)//清楚一個子樹 10 { 11 f[x]=cnt[x]=ch[x][0]=ch[x][1]=size[x]=key[x]=0; 12 } 13 14 bool get(int x)//確定本節點是父親的左孩子或右孩子 15 { 16 return ch[f[x]][1]==x; 17 } 18 19 void pushup(int x)//更新節點信息 20 { 21 if(x) 22 { 23 size[x]=cnt[x];//本節點的數量 24 if(ch[x][0]) 25 size[x]+=size[ch[x][0]];//左子樹的數量 26 if(ch[x][1]) 27 size[x]+=size[ch[x][1]];//右子樹的數量 28 } 29 } 30 31 void rotate(int x) 32 { 33 int old=f[x],oldf=f[old],which=get(x);//which為本節點與父節點的關係 34 35 ch[old][which]=ch[x][which^1];//本節點的“反which“儿子 成為 父親的”which“儿子 36 f[ch[old][which]]=old; 37 38 ch[x][which^1]=old;//父親成為x的“反which”儿子 39 f[old]=x; 40 41 f[x]=oldf;//x的父親是祖父 42 if(oldf) 43 ch[oldf][ch[oldf][1]==old]=x;//祖父的儿子是x 44 45 pushup(old);//更新 46 pushup(x); 47 48 } 49 50 void splay(int x) 51 { 52 for(int fa;fa=f[x];rotate(x)) 53 if(f[fa]) 54 rotate(get(x)==get(fa)?fa:x);//雙旋優化，三點一線，先旋父親 55 rt=x;//更新为根节点 56 } 57 58 void insert(int x) 59 { 60 if(rt==0)//如果空樹 61 { 62 sz++; 63 key[sz]=x; 64 rt=sz; 65 cnt[sz]=size[sz]=1; 66 f[sz]=ch[sz][0]=ch[sz][1]=0; 67 return; 68 } 69 int now=rt,fa=0; 70 while(1) 71 { 72 if(x==key[now])//如果x已存在,節點上的個數++ 73 { 74 cnt[now]++; 75 pushup(now); 76 pushup(fa); 77 splay(now); 78 return; 79 } 80 fa=now; 81 now=ch[now][x>key[now]];//根據平衡樹特性往下搜 82 if(!now)//如果不存在x，創建節點 83 { 84 sz++; 85 size[sz]=cnt[sz]=1; 86 ch[sz][0]=ch[sz][1]=0; 87 ch[fa][x>key[fa]]=sz; 88 f[sz]=fa; 89 key[sz]=x; 90 pushup(fa); 91 splay(sz); 92 return; 93 } 94 } 95 } 96 97 int rnk(int x) 98 { 99 int now=rt,ans=0; 100 while(now) 101 { 102 if(x<key[now])//如果比x的值，搜左子樹 103 now=ch[now][0]; 104 else 105 { 106 ans+=size[ch[now][0]];//否則先加上左子樹節點的數量 107 if(x==key[now])//如果x為所查詢節點 108 { 109 splay(now); 110 return ans+1; 111 } 112 ans+=cnt[now];//x不是所查詢節點 113 now=ch[now][1]; 114 } 115 } 116 printf("Not find ");//如果不存在該節點 117 return -1; 118 } 119 120 int kth(int x) 121 { 122 int now=rt; 123 while(now) 124 { 125 if(ch[now][0]&&x<=size[ch[now][0]])//如果左子树左子樹數量>當前排名 126 now=ch[now][0]; 127 else 128 { 129 int temp=size[ch[now][0]]+cnt[now]; 130 if(x<=temp)//左子樹加上本節點數量大於排名，本節點即所求 131 return key[now]; 132 x-=temp;//往右子樹搜 133 now=ch[now][1]; 134 } 135 } 136 printf("Not find "); 137 return -1; 138 } 139 140 int pre()//先把所求的節點splay位根節點，再用此函數得到前驅 141 { 142 int now=ch[rt][0]; 143 while(ch[now][1]) 144 now=ch[now][1]; 145 return now; 146 } 147 int next()//先splay，再得到後繼 148 { 149 int now=ch[rt][1]; 150 while(ch[now][0]) 151 now=ch[now][0]; 152 return now; 153 } 154 void del(int x) 155 { 156 int k=rnk(x);//先splay到根 157 if(k==-1)//如果不存在x 158 return ; 159 if(cnt[rt]>1)//若x的數量>1。只需要數量-- 160 { 161 cnt[rt]--; 162 pushup(rt); 163 return; 164 } 165 if(!ch[rt][0]&&!ch[rt][1])//如果沒有孩子，直接清除 166 { 167 clear(rt); 168 rt=0; 169 return; 170 } 171 if(!ch[rt][0])//如果只有一邊孩子，直接讓孩子頂替根節點 172 { 173 int oldrt=rt; 174 rt=ch[rt][1]; 175 f[rt]=0; 176 clear(oldrt); 177 return; 178 } 179 else if(!ch[rt][1]) 180 { 181 int oldrt=rt; 182 rt=ch[rt][0]; 183 f[rt]=0; 184 clear(oldrt); 185 return; 186 } 187 int oldrt=rt,leftbig=pre();//兩邊都有，則讓前驅作為根節點 188 splay(leftbig); 189 ch[rt][1]=ch[oldrt][1];//做相應的連接 190 f[ch[oldrt][1]]=rt; 191 clear(oldrt); 192 pushup(rt); 193 } 194 195 void show(int x)//升序輸出 196 { 197 if(ch[x][0]) 198 show(ch[x][0]); 199 for(int i=0;i<cnt[x];++i) 200 printf("%d ",key[x]); 201 if(ch[x][1]) 202 show(ch[x][1]); 203 } 204 int main() 205 { 206 int x; 207 char f[5]; 208 while(1) 209 { 210 scanf("%s",f); 211 if(f[0]=='q') 212 break; 213 else if(f[0]=='a')//插入 214 { 215 scanf("%d",&x); 216 insert(x); 217 } 218 else if(f[0]=='d')//刪除 219 { 220 scanf("%d",&x); 221 del(x); 222 } 223 else if(f[0]=='r')//查詢x的排名 224 { 225 scanf("%d",&x); 226 printf("rank : %d ",rnk(x)); 227 } 228 else if(f[0]=='k')//查詢排名為k的值 229 { 230 scanf("%d",&x); 231 printf("-> %d ",kth(x)); 232 } 233 puts(""); 234 printf("Now : "); 235 show(rt); 236 puts(""); 237 puts(""); 238 } 239 }