【数据结构】splay伸展树

引言

splay树并不是严格意义上的平衡树，但是他可以做到平衡树可以做到的一切。

而且，相比与RBT和AVL，splay简直不能更好写了～

所以，用来解决一般的算法问题，基本上splay已经是够用了。

splay

操作

关于splay的基本操作就是旋转，将一个子树向左或向右旋转。

关于两种旋转，可以参考这篇博客。

但是，从我个人理解，无论是左旋还是右旋，本质都是将一个节点上提（降低节点的深度）。

而旋转操作有用在区间操作上：我们可以通过旋转将一个区间旋转到一棵子树上，这样就可以直接对树根打上lazy标记。

实现

理解起来真的很简单，动手画图很好画，但是当要将这么多种情况都写成代码的时候，就十分痛苦了：有那么多种情况，每一种情况分类讨论其实挺简单的，但是…那也太丑了，不忍直视。

所以，只好找别的写好的模板自己改写一下，瞬间美观、简洁100倍！

splay经常会写出bug，所以直接找个题应用一下～

所以，模板就直接看应用吧～

应用

HDU1890，splay模板题～

自恋的吹一波，真心觉得这种风格的splay真的简洁～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define N 100010

struct PX {
    int va, id;
}px[N];

int rk[N], pos[N];
int son[N][2], fa[N], rev[N], sz[N];
int cnt, root, n;

bool cmp(const PX &a, const PX &b) {
    if (a.va == b.va) return a.id < b.id;
    return a.va < b.va;
}

bool cmp1(const PX &a, const PX &b) {
    return a.id < b.id;
}

void newnode(int y, int &x) {
    x = ++cnt;
    fa[x] = y;
    sz[x] = 1;
    rev[x] = false;
    son[x][0] = son[x][1] = 0;
}

void init() {
    cnt = 0;
    // 加入首尾节点方便提取区间
    newnode(0, root);// 1为首节点
    newnode(root, son[root][1]);// 2为末节点
    sz[root] = 2;
}

void reverse(int x) {
    if (!x) return;
    rev[x] ^= 1;// lazy
}

void pushup(int x) {
    sz[x] = sz[son[x][0]] + sz[son[x][1]] + 1;
}

void pushdown(int x) {
    if (!x || !rev[x]) return;
    rev[x] = false;
    reverse(son[x][0]);
    reverse(son[x][1]);
    swap(son[x][0], son[x][1]);
}

void build(int &x, int l, int r, int g) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    newnode(g, x);
    pos[rk[mid]] = x; // pos[i]排名为i的数字对应splay中的节点号
    build(son[x][0], l, mid - 1, x);
    build(son[x][1], mid + 1, r, x);
    pushup(x);
}

void link(int x, int y, int c) {
    fa[x] = y;
    son[y][c] = x;
}

void rotate(int x, int c) {
    int y = fa[x];
    pushdown(y);
    pushdown(x);
    link(x, fa[y], son[fa[y]][1] == y);
    link(son[x][!c], y, c);
    link(y, x, !c);
    pushup(y);
}

void splay(int x, int g) {
    pushdown(x);
    int y, cy, cx;
    while (fa[x] != g) {
        y = fa[x];
        pushdown(fa[y]);
        pushdown(y);
        pushdown(x);
        cy = son[fa[y]][1] == y;
        cx = son[y][1] == x;
        if (fa[y] == g) rotate(x, cx);
        else {
            if (cx == cy) rotate(y, cy);
            else rotate(x, cx);
            rotate(x, cy);
        }
    }
    pushup(x);
    if (!g) root = x;
}

int getmax(int x) {
    // 从上向下必须pushdown
    pushdown(x);
    while (son[x][1]) {
        x = son[x][1];
        pushdown(x);
    }
    return x;
}

void del() {
    int x = root;
    if (son[x][0] && son[x][1]) {
        int y = getmax(son[x][0]);
        splay(y, x);
        fa[y] = 0;
        root = y;
        fa[son[x][1]] = y;
        son[y][1] = son[x][1];
        pushup(y);
    }
    else if (son[x][0]) fa[son[x][0]] = x, root = son[x][0];
    else fa[son[x][1]] = x, root = son[x][1];
}

int main() {
    while (scanf("%d", &n), n) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &px[i].va);
            px[i].id = i;
        }
        sort(px + 1, px + 1 + n, cmp);
        for (int i = 1; i <= n; i++)
            rk[px[i].id] = i;// rk[x]表示原数组中索引为x的数的排名
        sort(px + 1, px + 1 + n, cmp1);
        init();
        build(son[son[root][1]][0], 1, n, son[root][1]);
        pushup(son[root][1]);
        pushup(root);
        for (int i = 1; i <= n; i++) {
            splay(pos[i], 0);
            splay(1, pos[i]);// root == pos[i]
            printf("%d", i + sz[son[1][1]]);
            if (i < n) printf(" ");
            rev[son[1][1]] ^= 1;
            del();// 对root操作不需要向上pushup
        }
        puts("");
    }
    return 0;
}

（待更新…）