【模板】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
", get_rank(x)); break;
179             case 4: printf("%d
", get_kth(x)); break;
180             case 5: insert(x); printf("%d
", w[get_pre()]); del(x); break;
181             case 6: insert(x); printf("%d
", 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
", 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