最近学了一下平衡树，想做一些笔记。
1.$Splay$
$Splay$是我学会的第一棵平衡树（滑稽）
$Splay$通过$Splay$操作，让$Splay$保持乱序，即“平衡”。
基本操作：
1.$pushup$/$pushdown$ 维护标记。$O(1)$
2.$rotate$ 上旋。$O(\log n)$
3.$splay$ 将节点向上移动。$O(1)$
模板
1 #include<cstdio> 2 #define MAXL 100003 3 #define INF (1 << 30) 4 using namespace std; 5 class Splay { 6 #define root e[0].ch[1] 7 private: 8 class node { 9 public: 10 int v, father, ch[2], recy, sum; 11 } e[MAXL]; 12 int n, points; 13 inline void update(int x){ 14 e[x].sum = e[e[x].ch[0]].sum + e[e[x].ch[1]].sum + e[x].recy; 15 } 16 inline int identify(int x){ 17 return e[e[x].father].ch[1] == x; 18 } 19 inline void connect(int x, int f, int son){ 20 e[f].ch[son] = x; 21 e[x].father = f; 22 } 23 inline void rotate(int x){ 24 int y = e[x].father, mroot = e[y].father, mrootson = identify(y), yson = identify(x), 25 B = e[x].ch[yson ^ 1]; 26 connect(B, y, yson);connect(y, x, yson ^ 1);connect(x, mroot, mrootson); 27 update(y);update(x); 28 } 29 inline void splay(int at, int to){ 30 to = e[to].father; 31 while(e[at].father != to){ 32 int up = e[at].father; 33 if(e[up].father == to) rotate(at); 34 else if(identify(at) == identify(up)){ 35 rotate(up);rotate(at); 36 } else { 37 rotate(at);rotate(at); 38 } 39 } 40 } 41 inline int crepoint(int v, int father){ 42 n ++; 43 e[n].v = v; 44 e[n].father = father; 45 e[n].sum = e[n].recy = 1; 46 return n; 47 } 48 inline void destroy(int x){ 49 e[x].v = e[x].father = e[x].ch[0] = e[x].ch[1] = e[x].recy = e[x].sum = 0; 50 if(x == n) n --; 51 } 52 public: 53 inline int getroot(){return root;} 54 inline int find(int v){ 55 int now = root; 56 while(true){ 57 if(e[now].v == v){ 58 splay(now, root); 59 return now; 60 } 61 int nxt = e[now].v < v; 62 if(!e[now].ch[nxt]) return 0; 63 now = e[now].ch[nxt]; 64 } 65 } 66 inline int build(int v){ 67 if(!points) n = 0; 68 points ++; 69 if(!n){ 70 root = 1; 71 return crepoint(v, 0); 72 } 73 int now = root; 74 while(true){ 75 e[now].sum ++; 76 if(e[now].v == v){ 77 e[now].recy ++; 78 return now; 79 } 80 int nxt = e[now].v < v; 81 if(!e[now].ch[nxt]) return e[now].ch[nxt] = crepoint(v, now); 82 now = e[now].ch[nxt]; 83 } 84 return 0; 85 } 86 inline void push(int v){ 87 splay(build(v), root); 88 } 89 inline void pop(int v){ 90 int deal = find(v); 91 if(!deal) return; 92 points --; 93 if(e[deal].recy > 1){ 94 e[deal].recy --; 95 e[deal].sum --; 96 return; 97 } 98 if(!e[deal].ch[0]){ 99 root = e[deal].ch[1]; 100 e[root].father = 0; 101 } else { 102 int lef = e[deal].ch[0]; 103 while(e[lef].ch[1]) lef = e[lef].ch[1]; 104 splay(lef, e[deal].ch[0]); 105 int rig = e[deal].ch[1]; 106 connect(rig, lef, 1);connect(lef, 0, 1); 107 update(lef); 108 } 109 destroy(deal); 110 } 111 inline int rank(int v){ 112 int ans = 1, now = root; 113 while(true){ 114 if(e[now].v == v){ 115 ans += e[e[now].ch[0]].sum; 116 break; 117 } 118 if(!now) break; 119 if(v < e[now].v) now = e[now].ch[0]; 120 else { 121 ans += e[e[now].ch[0]].sum + e[now].recy; 122 now = e[now].ch[1]; 123 } 124 } 125 if(now) splay(now, root); 126 return ans; 127 } 128 inline int atrank(int x){ 129 if(x > points) return INF; 130 int now = root; 131 while(true){ 132 int minused = e[now].sum - e[e[now].ch[1]].sum; 133 if(x > e[e[now].ch[0]].sum && x <= minused) break; 134 if(x <= minused) now = e[now].ch[0]; 135 else { 136 x -= minused; 137 now = e[now].ch[1]; 138 } 139 } 140 splay(now, root); 141 return e[now].v; 142 } 143 inline int lower(int v){ 144 int now = root, res = -INF; 145 while(now){ 146 if(e[now].v < v && e[now].v > res) res = e[now].v; 147 if(e[now].v >= v) now = e[now].ch[0]; 148 else now = e[now].ch[1]; 149 } 150 return res; 151 } 152 inline int upper(int v){ 153 int now = root, res = INF; 154 while(now){ 155 if(e[now].v > v && e[now].v < res) res = e[now].v; 156 if(e[now].v > v) now = e[now].ch[0]; 157 else now = e[now].ch[1]; 158 } 159 return res; 160 } 161 } sp; 162 int n; 163 int main(){ 164 scanf("%d", &n); 165 while(n --){ 166 int opt, x; 167 scanf("%d%d", &opt, &x); 168 switch(opt){ 169 case 1: 170 sp.push(x); 171 break; 172 case 2: 173 sp.pop(x); 174 break; 175 case 3: 176 printf("%d\n", sp.rank(x)); 177 break; 178 case 4: 179 printf("%d\n", sp.atrank(x)); 180 break; 181 case 5: 182 printf("%d\n", sp.lower(x)); 183 break; 184 case 6: 185 printf("%d\n", sp.upper(x)); 186 } 187 } 188 }
因为$Splay$操作，$Splay$是一种非常强大的序列区间操作的数据结构。
1 // 文艺平衡树 2 // luogu-judger-enable-o2 3 #include<cstdio> 4 #include<algorithm> 5 #define MAXL 100010 6 #define Rint register int 7 using namespace std; 8 int n, m; 9 struct Splay { 10 #define root e[0].ch[1] 11 struct node { 12 int v, father, ch[2], sum, tag; 13 } e[MAXL]; 14 int n; 15 Splay(): n(0){} 16 inline void update(int x){ 17 e[x].sum = e[e[x].ch[0]].sum + e[e[x].ch[1]].sum + 1; 18 } 19 inline void pushdown(int x){ 20 if(x && e[x].tag){ 21 e[e[x].ch[0]].tag ^= 1; 22 e[e[x].ch[1]].tag ^= 1; 23 swap(e[x].ch[0], e[x].ch[1]); 24 e[x].tag = 0; 25 } 26 } 27 inline int identify(int x){ 28 return e[e[x].father].ch[1] == x; 29 } 30 inline int crepoint(int v, int f){ 31 e[++ n].v = v; 32 e[n].father = f; 33 e[n].sum = 1; 34 e[n].tag = 0; 35 return n; 36 } 37 inline void connect(int x, int f, int son){ 38 e[f].ch[son] = x; 39 e[x].father = f; 40 } 41 inline void rotate(int x){ 42 int y = e[x].father, mroot = e[y].father, mrootson = identify(y), yson = identify(x), 43 B = e[x].ch[yson ^ 1]; 44 connect(B, y, yson);connect(y, x, yson ^ 1);connect(x, mroot, mrootson); 45 update(y);update(x); 46 } 47 inline void splay(int at, int to){ 48 while(e[at].father != to){ 49 int up = e[at].father; 50 if(e[up].father == to) rotate(at); 51 else if(identify(at) == identify(up)){ 52 rotate(up);rotate(at); 53 } else { 54 rotate(at);rotate(at); 55 } 56 } 57 } 58 inline int build(int fa, int l, int r){ 59 if(l > r) return 0; 60 int mid = l + r >> 1, now = crepoint(mid, fa); 61 if(!root) root = now; 62 e[now].ch[0] = build(now, l, mid - 1); 63 e[now].ch[1] = build(now, mid + 1, r); 64 update(now); 65 return now; 66 } 67 inline int atrank(int x){ 68 int now = root; 69 while(true){ 70 pushdown(now); 71 int minused = e[e[now].ch[0]].sum + 1; 72 if(x == minused) return now; 73 if(x < minused) now = e[now].ch[0]; 74 else { 75 x -= minused; 76 now = e[now].ch[1]; 77 } 78 } 79 } 80 inline void rev(int l, int r){ 81 l = atrank(l); 82 r = atrank(r + 2); 83 splay(l, 0); 84 splay(r, l); 85 e[e[e[root].ch[1]].ch[0]].tag ^= 1; 86 } 87 inline void write(int x){ 88 pushdown(x); 89 if(e[x].ch[0]) write(e[x].ch[0]); 90 if(e[x].v > 1 && e[x].v < ::n + 2) printf("%d ", e[x].v - 1); 91 if(e[x].ch[1]) write(e[x].ch[1]); 92 } 93 } sp; 94 int main(){ 95 scanf("%d%d", &n, &m); 96 sp.build(0, 1, n + 2); 97 while(m --){ 98 int l, r; 99 scanf("%d%d", &l, &r); 100 sp.rev(l, r); 101 } 102 sp.write(sp.root); 103 }
原文：https://www.cnblogs.com/AThousandMoons/p/10053001.html
