【模板】splay
?
看她的博客好了http://blog.csdn.net/Clove_unique/article/details/50630280?locationNum=1&fps=1
還有一個http://blog.csdn.net/fate_zero_saber/article/details/56496660
最后一個http://m.blog.csdn.net/article/details?id=49978643
反正我也懶得寫。
?
摘錄一些：
splay很靈活的，它既可以作為一棵二叉查找樹又可以作為一棵區間樹，不過不能共存。?因此從兩方面來說splay。?一、splay的rotate，splay操作?splay不是特別平衡。不過splay還算是平衡樹吧，是有維護平衡的方式的。?splay維護平衡的方式就是提根。查詢完了某個節點，就把這個節點提根。這樣經過證明每次操作是均攤log(n)的。?提根就是不停旋轉，一次旋轉，目標節點總可以被轉上去一層，然后最終會到根。單旋和其他平衡樹一樣。?然后注意splay比別的平衡樹多了2種雙旋，即zigzig和zagzag。?為什么呢？因為如果原來splay是一條鏈（且是一條直鏈，即左兒子連左兒子一直連下去），把鏈的尾部提根，如果像別的平衡樹一樣旋轉（自底向上）那么轉完了還是一條鏈，高度沒有降低，最壞是O(n)的。?對于這種情況，zigzig和zagzag就有用了。?這種雙旋是這樣來的：
??
如果我們把最下面的點提根，那就要先zig目標節點的父親，再zig目標節點。（不同于自底向上zig）?這樣樹的高度縮小了。只需要我們多一個維護當前節點的父親。?總結一下，單旋和以前一樣，不過要維護父親。?提根(splay)操作，把當前節點轉成目標節點的兒子。?如果目標節點（一般是0，即轉成根；有時是根，即轉成根的兒子）不是當前點的父親的父親，那么就要雙旋。折線形就zigzag，zagzig，直線形就是zigzig，zagzag。?如果是，那么就只單旋一次退出循環。
?
?二、平衡樹?
splay作為平衡樹，可以O(logn)完成普通平衡樹支持的所有操作。并且由于其支持區間樹的特性，很多操作都有兩種以上的寫法。?
插入：與二叉查找樹類似。最后要提根。?
求前驅：有很多寫法了。可以從根向下找（類似于二叉查找樹find），找到key[x] < val的就更新。也可以find到目標點，然后提根，在根的左子樹里面找最大值。?
求后繼：同上。?
求x的排名：有很多寫法了。可以從根向下找，跑到右邊子樹去了就得+左邊的size+根的tot，還可以找到x的前驅，把x的前驅提根，返回此時左邊的size+根的tot+1。?
求第k大：這個貌似還是像以前一樣，從根向下找。?
刪除x：好像用以前的二叉查找樹的方法也可以。。不過還有更簡單的，就是找到x的前驅，提根，找到x的后繼，提到右兒子。刪掉根的右兒子的左兒子，即x。刪一段區間也可以這么來，感覺比較像區間樹了。?
三、可重平衡樹?
這個和以前一樣了，維護一個tot域，然后就可以做了。?
沒有SBT維護tot域麻煩因為這個sz沒有兩個意思，刪除操作不用以前的，就用提根這樣來刪代碼不怎么復雜。?
四、pushup和pushdown?
splay的旋轉是把一個點向上轉，那么需要pushup?
pushup主要是在平衡樹rotate，splay的時候調用，區間樹也是rotate，splay的時候調用，有個build也會用，對某個子區間操作后還要pushup上去更新全區間。?
在平衡樹中，pushup主要維護一個size?
在區間樹中，pushup主要維護和別的與兒子有關的參數例如size，min，max，sum，rl（右側子串長）,ll（左側子串長），maxl（拼合后整個區間子串長）等等，比較像線段樹。?
不過一定要注意，splay的父節點也要參與其中。?
如線段樹維護一個sum：
tree[x].sum=tree[2*x].sum+tree[2*x+1].sum;splay維護一個sum：
sum[x]=v[ch[x][0]]+v[ch[x][0]]+v[x];平衡樹很少有pushdown。?
區間樹的pushdown和線段樹很像。主要是一個lazy標記。比如rev（翻轉標記），delta（區間增加標記）等等。?
因為區間翻轉，就是左右子樹交換，遞歸下去，繼續左右子樹交換，直到葉子。但是lazy操作，只把rev標記打在一段區間上，如果要訪問這個區間的子區間，即在樹上往下走時，再交換左右子樹把rev消除掉。delta同理，先打在根上，還有往下走再把根的左右兒子加上delta，把根的delta重置。?
因此，pushdown操作主要是發生在從根往下走，走到兒子前pushdown一次。?
五、區間樹?
區間樹主要維護一個數列。也可以認為它是一棵二叉查找樹，不過key值變成了數列中的下標而非實值。?
不過這樣不怎么好寫。。比如在第x個數后面插入一個y。下標就變了。?
因此寫區間樹就不要想著平衡樹，因此，splay就不支持動態區間第k大這種。?
區間樹還有一個rotateto（x，goal）操作。就是把當前數列中第x個元素提到goal位置。實現就是平衡樹的第k大找到節點后splay。再說一遍，這個不需要專門維護下標，只需要size就可以了。?
?
有了這些，區間樹支持以下操作：?
1.insert(x,y)在第x個數后面插入一個y。就是rotateto(x,0),rotateto(x+1,root)。然后新建一個節點接在根的右兒子的左兒子上面，完了記得pushup，后面不重復提醒了。?
2.delete(l,r)刪除位置為[l,r]的所有數。就是rotateto(l-1,0),rotateto(r+1,root)。然后以根的右兒子的左兒子為根的子樹全砍掉。?
3.add(l,r)把位置為[l,r]的所有數+1。就是rotateto(l-1,0),rotateto(r+1,root)。根的右兒子的左兒子的delta++。?
4.reverse(l,r)翻轉位置為[l,r]的所有數。就是rotateto(l-1,0),rotateto(r+1,root)。根的右兒子的左兒子的rev^=1。?
5.min/max/sum(l,r)返回位置為[l,r]的所有數的最小/最大/和。就是rotateto(l-1,0),rotateto(r+1,root)。根的右兒子的左兒子的min/max/sum。?
?
洛谷模板題
支持操作：
1.插入x數
2.刪除x數(若有多個相同的數，因只刪除一個)
3.查詢x數的排名(若有多個相同的數，因輸出最小的排名)
4.查詢排名為x的數
5.求x的前驅(前驅定義為小于x，且最大的數)
6.求x的后繼(后繼定義為大于x，且最小的數)
——代碼
1 #include <cstdio> 2 3 using namespace std; 4 5 const int N = 300005; 6 int n, root, sz; 7 int w[N], cnt[N], size[N], son[N][2], f[N]; 8 9 void clear(int x) 10 { 11 son[x][0] = son[x][1] = f[x] = cnt[x] = w[x] = size[x] = 0; 12 } 13 14 int get(int x) 15 { 16 return son[f[x]][1] == x; 17 } 18 19 void update(int x) 20 { 21 size[x] = cnt[x] + size[son[x][0]] + size[son[x][1]]; 22 } 23 24 void rotate(int x) 25 { 26 int old = f[x], oldf = f[old], wh = get(x); 27 son[old][wh] = son[x][wh ^ 1]; 28 if(son[old][wh]) f[son[old][wh]] = old; 29 son[x][wh ^ 1] = old; 30 f[old] = x; 31 if(oldf) son[oldf][son[oldf][1] == old] = x; 32 f[x] = oldf; 33 update(old); 34 update(x); 35 } 36 37 void splay(int x) 38 { 39 for(int fa; fa = f[x]; rotate(x)) 40 if(f[fa]) 41 rotate((get(x) == get(fa)) ? fa : x); 42 root = x; 43 } 44 45 void insert(int x) 46 { 47 if(!root) 48 { 49 root = ++sz; 50 w[sz] = x; 51 cnt[sz] = size[sz] = 1; 52 return; 53 } 54 int now = root, fa = 0; 55 while(1) 56 { 57 if(w[now] == x) 58 { 59 cnt[now]++; 60 update(now); 61 splay(now); 62 break; 63 } 64 fa = now; 65 now = son[now][x > w[now]]; 66 if(!now) 67 { 68 sz++; 69 w[sz] = x; 70 f[sz] = fa; 71 cnt[sz] = size[sz] = 1; 72 son[fa][x > w[fa]] = sz; 73 update(fa); 74 splay(sz); 75 break; 76 } 77 } 78 } 79 80 int get_rank(int x) 81 { 82 int ans = 0, now = root; 83 while(1) 84 { 85 if(x < w[now]) now = son[now][0]; 86 else 87 { 88 ans += size[son[now][0]]; 89 if(w[now] == x) 90 { 91 splay(now); 92 return ans + 1; 93 } 94 ans += cnt[now]; 95 now = son[now][1]; 96 } 97 } 98 } 99 100 int get_kth(int x) 101 { 102 int now = root; 103 while(1) 104 { 105 if(x <= size[son[now][0]]) now = son[now][0]; 106 else 107 { 108 x -= size[son[now][0]]; 109 if(x <= cnt[now]) 110 { 111 splay(now); 112 return w[now]; 113 } 114 x -= cnt[now]; 115 now = son[now][1]; 116 } 117 } 118 } 119 120 int get_pre() 121 { 122 int now = son[root][0]; 123 while(son[now][1]) now = son[now][1]; 124 return now; 125 } 126 127 int get_suc() 128 { 129 int now = son[root][1]; 130 while(son[now][0]) now = son[now][0]; 131 return now; 132 } 133 134 void del(int x) 135 { 136 int oldroot, leftbig, wh = get_rank(x); 137 if(cnt[root] > 1) 138 { 139 cnt[root]--; 140 update(root); 141 return; 142 } 143 if(!son[root][0] && !son[root][1]) 144 { 145 clear(root); 146 root = 0; 147 return; 148 } 149 if(!son[root][0] || !son[root][1]) 150 { 151 oldroot = root; 152 root = son[root][0] + son[root][1]; 153 f[root] = 0; 154 clear(oldroot); 155 return; 156 } 157 oldroot = root; 158 leftbig = get_pre(); 159 splay(leftbig); 160 son[root][1] = son[oldroot][1]; 161 f[son[root][1]] = root; 162 clear(oldroot); 163 update(root); 164 return; 165 } 166 167 int main() 168 { 169 int i, opt, x; 170 scanf("%d", &n); 171 for(i = 1; i <= n; i++) 172 { 173 scanf("%d %d", &opt, &x); 174 switch(opt) 175 { 176 case 1: insert(x); break; 177 case 2: del(x); break; 178 case 3: printf("%d\n", get_rank(x)); break; 179 case 4: printf("%d\n", get_kth(x)); break; 180 case 5: insert(x); printf("%d\n", w[get_pre()]); del(x); break; 181 case 6: insert(x); printf("%d\n", w[get_suc()]); del(x); break; 182 } 183 } 184 return 0; 185 } View Code?
?
Pku模板題
又需要支持區間加，區間翻轉，區間平移，指定位置插入一個數，刪除一個區間，區間求最小值。
區間平移的話，如果把區間向右平移 t 位，先把 t % 區間長度，防止平移回來，這樣就相當于把后面的 t 個數字挪到區間前面，來先把 [ y - t + 1, y ] 旋轉出來，刪除然后插入到 [ x, y - t] 區間的前面。就完成了。
——代碼
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 #define N 300005 7 #define INF 2100000000 8 9 int n, m, d, root, sz, aa, bb; 10 int a[N], f[N], son[N][2], size[N], Min[N], key[N], add[N], rev[N]; 11 char opt[20]; 12 13 //刪除 14 inline void clear(int x) 15 { 16 f[x] = son[x][0] = son[x][1] = size[x] = Min[x] = key[x] = add[x] = rev[x] = 0; 17 } 18 19 //判斷 x 是父親的哪個兒子 20 inline int get(int x) 21 { 22 return son[f[x]][1] == x; 23 } 24 25 inline void update(int x) 26 { 27 size[x] = size[son[x][0]] + size[son[x][1]] + 1; 28 Min[x] = key[x]; 29 if(son[x][0]) Min[x] = min(Min[x], Min[son[x][0]]); 30 if(son[x][1]) Min[x] = min(Min[x], Min[son[x][1]]); 31 } 32 33 //建樹 34 inline int build(int l, int r, int fa) 35 { 36 if(l > r) return 0; 37 int mid = (l + r) >> 1, now = ++sz; 38 f[sz] = fa, key[sz] = a[mid]; 39 int lch = build(l, mid - 1, now); 40 int rch = build(mid + 1, r, now); 41 son[now][0] = lch, son[now][1] = rch; 42 update(now); 43 return now; 44 } 45 46 //標記下放 47 inline void pushdown(int x) 48 { 49 if(!x) return; 50 if(rev[x]) 51 { 52 rev[son[x][0]] ^= 1; 53 rev[son[x][1]] ^= 1; 54 swap(son[x][0], son[x][1]); 55 rev[x] = 0; 56 } 57 if(add[x]) 58 { 59 add[son[x][0]] += add[x], add[son[x][1]] += add[x]; 60 Min[son[x][0]] += add[x], Min[son[x][1]] += add[x]; 61 key[son[x][0]] += add[x], key[son[x][1]] += add[x]; 62 add[x] = 0; 63 } 64 } 65 66 //查找排名為 x 的數 67 inline int find(int x) 68 { 69 int now = root; 70 while(1) 71 { 72 pushdown(now); 73 if(x <= size[son[now][0]]) now = son[now][0]; 74 else 75 { 76 x -= size[son[now][0]]; 77 if(x == 1) return now; 78 x--; 79 now = son[now][1]; 80 } 81 } 82 } 83 84 //旋轉 85 inline void rotate(int x) 86 { 87 pushdown(f[x]); 88 pushdown(x); 89 int old = f[x], oldf = f[old], wh = get(x); 90 son[old][wh] = son[x][wh ^ 1]; 91 f[son[old][wh]] = old; 92 son[x][wh ^ 1] = old; 93 f[old] = x; 94 if(oldf) son[oldf][son[oldf][1] == old] = x; 95 f[x] = oldf; 96 update(old); 97 update(x); 98 } 99 100 //mplay ?? 101 inline void splay(int x,int to) 102 { 103 for(int fa; (fa = f[x]) != to; rotate(x)) 104 if(f[fa] != to) 105 rotate(get(fa) == get(x) ? fa : x); 106 if(!to) root = x; 107 } 108 109 //區間加 110 inline void Add(int x, int y) 111 { 112 if(x > y) swap(x, y); 113 aa = find(x);//第 x - 1 個到根節點 114 bb = find(y + 2);//第 y + 1 個到根節點右子樹 115 splay(aa, 0); 116 splay(bb, aa); 117 Min[son[son[root][1]][0]] += d; 118 add[son[son[root][1]][0]] += d; 119 key[son[son[root][1]][0]] += d; 120 update(son[root][1]); 121 update(root); 122 } 123 124 //區間翻轉 125 inline void reverse(int x, int y) 126 { 127 if(x == y) return; 128 if(x > y) swap(x ,y); 129 aa = find(x); 130 bb = find(y + 2); 131 splay(aa, 0); 132 splay(bb, aa); 133 rev[son[son[root][1]][0]] ^= 1; 134 } 135 136 //區間向右平移 t 位 137 //先把 t % 區間長度，防止平移回來 138 //這樣就相當于把后面的 t 個數字挪到區間前面來 139 //先把 [ y - t + 1, y ] 旋轉出來 140 //然后插入到 [ x, y - t ] 區間的前面 141 inline void revolve(int x, int y, int t) 142 { 143 if(x > y) swap(x, y); 144 t %= y - x + 1; 145 if(!t) return; //平移回初始。。 146 aa = find(y - t + 1); 147 bb = find(y + 2); 148 splay(aa, 0); 149 splay(bb, aa); 150 int now = son[son[root][1]][0]; 151 son[son[root][1]][0] = 0; 152 update(son[root][1]); 153 update(root); 154 aa = find(x); 155 bb = find(x + 1); 156 splay(aa, 0); 157 splay(bb, aa); 158 son[son[root][1]][0] = now; 159 f[now] = son[root][1]; 160 update(son[root][1]); 161 update(root); 162 } 163 164 inline void insert(int x, int y) 165 { 166 aa = find(x + 1); 167 bb = find(x + 2); 168 splay(aa, 0); 169 splay(bb, aa); 170 son[son[root][1]][0] = ++sz; 171 f[sz] = son[root][1]; 172 key[sz] = Min[sz] = y; 173 size[sz] = 1; 174 update(son[root][1]); 175 update(root); 176 } 177 178 inline void del(int x) 179 { 180 aa = find(x); 181 bb = find(x + 2); 182 splay(aa, 0); 183 splay(bb, aa); 184 int now = son[son[root][1]][0]; 185 clear(now); 186 son[son[root][1]][0] = 0; 187 update(son[root][1]); 188 update(root); 189 } 190 191 inline int get_min(int x, int y) 192 { 193 if(x > y) swap(x, y); 194 aa = find(x); 195 bb = find(y + 2); 196 splay(aa, 0); 197 splay(bb, aa); 198 return Min[son[son[root][1]][0]]; 199 } 200 201 int main() 202 { 203 int i, j, x, y, z; 204 scanf("%d", &n); 205 a[1] = -INF, a[n + 2] = INF; 206 for(i = 1; i <= n; i++) scanf("%d", &a[i + 1]); 207 root = build(1, n + 2, 0); 208 scanf("%d", &m); 209 for(i = 1; i <= m; i++) 210 { 211 scanf("%s", opt); 212 switch(opt[0]) 213 { 214 case 'A': scanf("%d %d %d", &x, &y, &d); Add(x, y); break; 215 case 'R': 216 { 217 if(opt[3] == 'E') 218 { 219 scanf("%d %d", &x, &y); 220 reverse(x, y); 221 } 222 else 223 { 224 scanf("%d %d %d", &x, &y, &z); 225 revolve(x, y, z); 226 } 227 break; 228 } 229 case 'I': scanf("%d %d", &x, &y); insert(x, y); break; 230 case 'D': scanf("%d", &x); del(x); break; 231 case 'M': scanf("%d %d", &x, &y); printf("%d\n", get_min(x, y)); break; 232 } 233 } 234 return 0; 235 } View Code?
洛谷模板題（區間翻轉）
——代碼
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 const int N = 100001; 7 const int INF = 23333333; 8 int n, m, root, sz, aa, bb; 9 int a[N], key[N], f[N], size[N], son[N][2], rev[N]; 10 11 inline void update(int x) 12 { 13 size[x] = size[son[x][0]] + size[son[x][1]] + 1; 14 } 15 16 inline int build(int l, int r, int fa) 17 { 18 if(l > r) return 0; 19 int mid = (l + r) >> 1, now = ++sz; 20 key[now] = a[mid], f[now] = fa; 21 int lc = build(l, mid - 1, now); 22 int rc = build(mid + 1, r, now); 23 son[now][0] = lc, son[now][1] = rc; 24 update(now); 25 return now; 26 } 27 28 inline void pushdown(int x) 29 { 30 if(!x) return; 31 if(rev[x]) 32 { 33 rev[son[x][0]] ^= 1; 34 rev[son[x][1]] ^= 1; 35 swap(son[x][0], son[x][1]); 36 rev[x] = 0; 37 } 38 } 39 40 inline int find(int x) 41 { 42 int now = root; 43 while(1) 44 { 45 pushdown(now); 46 if(x <= size[son[now][0]]) now = son[now][0]; 47 else 48 { 49 x -= size[son[now][0]]; 50 if(x == 1) return now; 51 x--; 52 now = son[now][1]; 53 } 54 } 55 } 56 57 inline int get(int x) 58 { 59 return x == son[f[x]][1]; 60 } 61 62 inline void rotate(int x) 63 { 64 pushdown(f[x]); 65 pushdown(x); 66 int old = f[x], oldf = f[old], wh = get(x); 67 son[old][wh] = son[x][wh ^ 1]; 68 f[son[old][wh]] = old; 69 son[x][wh ^ 1] = old; 70 f[old] = x; 71 if(oldf) son[oldf][son[oldf][1] == old] = x; 72 f[x] = oldf; 73 update(old); 74 update(x); 75 } 76 77 inline void splay(int x, int to) 78 { 79 for(int fa; (fa = f[x]) != to; rotate(x)) 80 if(f[fa] != to) 81 rotate(get(x) == get(fa) ? fa : x); 82 if(!to) root = x; 83 } 84 85 inline void reverse(int x, int y) 86 { 87 if(x == y) return; 88 if(x > y) swap(x, y); 89 aa = find(x); 90 bb = find(y + 2); 91 splay(aa, 0); 92 splay(bb, aa); 93 rev[son[son[root][1]][0]] ^= 1; 94 } 95 96 inline void print(int now) 97 { 98 pushdown(now); 99 if(son[now][0]) print(son[now][0]); 100 if(key[now] != INF && key[now] != -INF) printf("%d ", key[now]); 101 if(son[now][1]) print(son[now][1]); 102 } 103 104 int main() 105 { 106 int i, x, y; 107 scanf("%d %d", &n, &m); 108 a[1] = -INF, a[n + 2] = INF; 109 for(i = 1; i <= n; i++) a[i + 1] = i; 110 root = build(1, n + 2, 0); 111 for(i = 1; i <= m; i++) 112 { 113 scanf("%d %d", &x, &y); 114 reverse(x, y); 115 } 116 print(root); 117 return 0; 118 } View Code?
轉載于:https://www.cnblogs.com/zhenghaotian/p/6735155.html
總結
- 上一篇： [050] 微信公众平台开发入门视频教程
- 下一篇： 【概率论系列学习】泊松分布和指数分布的关