平衡树

发表于 分类于
  • 平衡树

平衡树

splay

伸展树特点就是每次操作完一个节点，将其旋转至根，保证BST性质的同时保持平衡不至于退化成链。对于一条长链，底端的节点旋转至顶会让这条链被压缩。

旋转rotate操作，分为左旋与右旋

伸展splay操作是旋转的组合，将某子树内节点x变为根节点。

  • 当x已经成为根的子节点时，做单次旋转
  • 否则存在x的父节点y，爷节点z
    • x-y-z处于一条“直链”，则先旋转y再旋转x
    • x-y-z处于一条“折链”，则先旋转x再旋转x

P3369 【模板】普通平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

  1. 插入 $x$ 数
  2. 删除 $x$ 数(若有多个相同的数，应只删除一个)
  3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$ )
  4. 查询排名为 $x$ 的数
  5. 求 $x$ 的前驱(前驱定义为小于 $x$，且最大的数)
  6. 求 $x$ 的后继(后继定义为大于 $x$，且最小的数)

基于伸展操作，可以实现以下操作

  • 插入x。二叉查找树的性质可以找到x，让节点计数值自增；否则若x不存在，则会增加一个叶子x。然后为了保证不退化成链，让x旋转至根。
  • 删除x。让x前驱旋转至根，再让x后继旋转至根的右儿子，此时x必是叶子。减少x节点计数值，若为0则直接删除节点x。
  • 找到x的排名。x旋转至根，则左子树的大小+1就是x的排名。（注意具体实现时，会添加正负无穷哨兵避免边界特判的复杂实现）
  • 找到排名为r的值。基于各子树大小与二叉查找树的性质实现。
  • 找到x的前驱/后继。让x旋转至根，找左/右子树中的最大/小值即为前驱/后继。

所有操作均摊$O(logn)$

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
158
159
160
161
162
163
164
// https://www.luogu.com.cn/problem/P3369
#include <iostream>
using namespace std;

#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
const int N = 1100010, INF = (1 << 30) + 1;
struct node {
    int s[2];  // 左右儿子
    int p;     // 父亲
    int v;     // 节点权值
    int cnt;   // 权值出现次数
    int siz;   // 子树大小
    void init(int p1, int v1) {
        p = p1, v = v1;
        cnt = siz = 1;
    }
} tr[N];

int root;  // 根节点编号
int idx;   // 节点个数

void pushup(int x) {
    tr[x].siz = tr[ls(x)].siz + tr[rs(x)].siz + tr[x].cnt;
}

// 左/右旋 6个指针的断开重连
void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1];
    tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y;
    tr[y].p = x;
    pushup(y), pushup(x);
}

// 将x不断旋转至k的儿子，k为0则x变为根
void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)  // 折转底，直转中
            (ls(y) == x) ^ (ls(z) == y) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (!k)
        root = x;
}

// 先二分查找，找到v则自增，否则添加新节点v（添加的位置必为叶子），并将v旋转至根
void insert(int v) {  // 插入
    int x = root, p = 0;
    while (x && tr[x].v != v)
        p = x, x = tr[x].s[v > tr[x].v];
    if (x)
        tr[x].cnt++;
    else {
        x = ++idx;
        if (p)
            tr[p].s[v > tr[p].v] = x;
        tr[x].init(p, v);
    }
    splay(x, 0);
}

// 二分找到值为v的节点，然后旋转至根。
// v不存在，返回 小于v的最大值 或 大于v的最小值 节点
void find(int v) {  // 找到v并转到根
    int x = root;
    while (tr[x].s[v > tr[x].v] && v != tr[x].v)
        x = tr[x].s[v > tr[x].v];
    splay(x, 0);
}

// find(v)，根节点值小于v，则根节点就是v的前驱
// 否则根左子树的最大值为前驱
int getpre(int v) {  // 前驱
    find(v);
    int x = root;
    if (tr[x].v < v)
        return x;
    x = ls(x);
    while (rs(x))
        x = rs(x);
    splay(x, 0);
    return x;
}

// find(v)，根节点值大于v，则根节点就是v的后继
// 否则根右子树的最小值为后继
int getsuc(int v) {  // 后继
    find(v);
    int x = root;
    if (tr[x].v > v)
        return x;
    x = rs(x);
    while (ls(x))
        x = ls(x);
    splay(x, 0);
    return x;
}

// 找到v的前驱和后继，让前驱成为根，后继成为根的右儿子
// 由于v的前驱后继唯一，所以此时v必为叶子节点。
void del(int v) {  // 删除
    int pre = getpre(v);
    int suc = getsuc(v);
    splay(pre, 0), splay(suc, pre);
    int del = tr[suc].s[0];
    if (tr[del].cnt > 1)
        tr[del].cnt--, splay(del, 0);
    else
        tr[suc].s[0] = 0, splay(suc, 0);
}

// 值为v在树中的排名，其左子树的大小就是排名（负无穷哨兵的存在）
int getrank(int v) {  // 排名
    insert(v);
    int res = tr[tr[root].s[0]].siz;
    del(v);
    return res;
}

// 获取排名为k的值，二分
int getval(int k) {  // 数值
    int x = root;
    while (true) {
        if (k <= tr[ls(x)].siz)  // 其必在左子树
            x = ls(x);
        else if (k <= tr[ls(x)].siz + tr[x].cnt)
            break;
        else
            k -= tr[ls(x)].siz + tr[x].cnt, x = rs(x);
    }
    splay(x, 0);
    return tr[x].v;
}
// 插入哨兵 insert(-INF), insert(INF)
// 插入，删除，查询节点值x排名，查询排名x的节点值，查询节点值x的前驱和后继节点值

int main() {
    insert(-INF);
    insert(INF);  // 哨兵
    int n, op, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &op, &x);
        if (op == 1)
            insert(x);
        else if (op == 2)
            del(x);
        else if (op == 3)
            printf("%d\n", getrank(x));
        else if (op == 4)
            printf("%d\n", getval(x + 1));
        else if (op == 5)
            printf("%d\n", tr[getpre(x)].v);
        else
            printf("%d\n", tr[getsuc(x)].v);
    }
    return 0;
}

P3391 【模板】文艺平衡树

您需要写一种数据结构，来维护一个有序数列。
其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。
第一行两个正整数 $n,m$，表示序列长度与操作个数。序列中第 $i$ 项初始为 $i$。
接下来 $m$ 行，每行两个正整数 $l,r$，表示翻转的区间。
输出一行 $n$ 个正整数，表示原始序列经过 $m$ 次变换后的结果。

对于已经构成的二叉树，其中序遍历是原有序列，我们对区间的反转实际是对其中一颗子树的反转？实际并不是。与线段树类似一个区间可能覆盖了多颗子树。

但是我们可以利用splay操作将区间[l,r] 内的节点聚集在一颗子树上。具体做法就是找到排名为l-1的节点编号x，找到排名为r+1的节点编号y。通过伸展操作让x为根，y为x的右儿子。这时区间[l,r] 所有节点都在y的左子树上。

我们要反转区间[l,r] 。只需对这颗子树的反转，可以为其打上懒标记。懒标记的作用在于当遍历到含懒标记的节点时交换左右儿子，并传递懒标记。对于打上偶数次懒标记相当于交换偶数次，也就是无需交换。

我们发现本题构造了一颗二叉平衡树，但是却不是二叉搜索树（反转操作后，中序遍历二叉树并不是有序的）。但是找到排名为k的节点编号却可以用二叉搜索实现，其二叉搜索的条件取决于子树的节点数目而不是子节点的值。

我们找到排名为k的节点编号x，然后将x旋转至根，这个过程中时不会遇到懒标记的，因为在找x的过程中所经过的节点都会处理懒标记。所以x旋转至根的这条链上不会遇到懒标记。

最后中序遍历输出，过程中遇到懒标记便处理并下传。

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
// https://www.luogu.com.cn/problem/P3391
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 100005
#define MOD 998244353
#define INF 0x3f3f3f3f
#define NINF 0xf3f3f3f3
using namespace std;

#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]

struct node {
    int s[2];  // 左右儿子
    int p;     // 父亲
    int v;     // 节点权值
    int siz;   // 子树大小
    int tag;
    void init(int p1, int v1) {
        p = p1, v = v1;
        siz = 1;
        tag = 0;
    }
} tr[N];

int root;  // 根节点编号
int idx;   // 节点个数

void pushup(int x) {
    tr[x].siz = tr[ls(x)].siz + tr[rs(x)].siz + 1;
}

void pushdown(int x) {
    if (tr[x].tag) {
        swap(ls(x), rs(x));
        tr[ls(x)].tag ^= 1;
        tr[rs(x)].tag ^= 1;
        tr[x].tag = 0;
    }
}

// 左/右旋 6个指针的断开重连
void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1];
    tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y;
    tr[y].p = x;
    pushup(y), pushup(x);
}

// 将x不断旋转至k的儿子，k为0则x变为根
void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)  // 折转底，直转中
            (ls(y) == x) ^ (ls(z) == y) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (!k)
        root = x;
}

// 先二分查找，找到v则自增，否则添加新节点v（添加的位置必为叶子），并将v旋转至根
void insert(int v) {  // 插入
    int x = root, p = 0;
    while (x && tr[x].v != v)
        p = x, x = tr[x].s[v > tr[x].v];
    x = ++idx;
    if (p)
        tr[p].s[v > tr[p].v] = x;
    tr[x].init(p, v);
    splay(x, 0);
}

// 获取排名为k的节点编号
int getid(int k) {
    int x = root;
    while (true) {
        pushdown(x);
        if (k <= tr[ls(x)].siz)  // 其必在左子树
            x = ls(x);
        else if (k == tr[ls(x)].siz + 1)
            break;
        else
            k -= tr[ls(x)].siz + 1, x = rs(x);
    }
    return x;
}

void dfs(int o) {
    if (!o)
        return;
    pushdown(o);
    dfs(ls(o));
    if (tr[o].v != INF && tr[o].v != NINF)
        cout << tr[o].v << " ";
    dfs(rs(o));
}

void sol() {
    insert(NINF);
    insert(INF);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        insert(i);
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        // 将排名为 [l+1, r+1] 聚集到一颗子树上，然后打上懒标记
        int x = getid(l), y = getid(r + 2);
        splay(x, 0);
        splay(y, x);
        tr[ls(y)].tag ^= 1;
    }
    dfs(root);
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

FHQ Treap

无旋Treap每颗子树内，节点权值val满足二叉查找树的性质，节点随机值key满足堆的性质。节点的随机值保证了形成的树不会退化成链较为平衡。

通过分割操作将一颗树分为两颗treap树x和y，x树内节点值均小于等于v，y树内节点值均大于v。

通过合并操作将两颗treap树合为一颗treap树。

P3369 【模板】普通平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

  1. 插入 $x$ 数
  2. 删除 $x$ 数(若有多个相同的数，应只删除一个)
  3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$ )
  4. 查询排名为 $x$ 的数
  5. 求 $x$ 的前驱(前驱定义为小于 $x$，且最大的数)
  6. 求 $x$ 的后继(后继定义为大于 $x$，且最小的数)

通过分割与合并可以实现：

  • 插入x。直接以x作为分割点分割成两树，然后将x视为一颗树，将三颗树合并即可。
  • 删除x。先分割成三颗树a,b,c，a树内节点值均小于x，b树内节点值等于x，c树内节点均大于x。随后让b树两子节点合并成为新的b树。这样相当于删除了b树的根节点，然后让a,b,c三树合并。
  • 找到x的排名。分割出节点值均小于x的树a，a的大小+1就是当前x的排名。
  • 找到排名为r的值。利用子树大小与BST的性质，二叉查找。
  • 找到x的前驱/后继。分割出节点值小/大于x的树a，a中最大/小值为x的前驱/后继
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
// https://www.luogu.com.cn/problem/P3369
#include <iostream>
using namespace std;

const int N = 100005;
struct node {
    int l, r;  // 左右儿子
    int val;   // 树的权值
    int rnd;   // 堆的随机值
    int size;  // 子树大小
} tr[N];
int root, idx;

void newnode(int& x, int v) {
    x = ++idx;
    tr[x].val = v;
    tr[x].rnd = rand();
    tr[x].size = 1;
}

void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

// 从根节点p开始将树分裂成以x为根和y为根的两棵树
// x树内节点值均小于等于v，y树内节点值均大于v
void split(int p, int v, int& x, int& y) {
    if (!p) {
        x = y = 0;
        return;
    }
    if (tr[p].val <= v) {
        x = p;
        split(tr[x].r, v, tr[x].r, y);
        pushup(x);
    } else {
        y = p;
        split(tr[y].l, v, x, tr[y].l);
        pushup(y);
    }
}

// x树和y树合并成新树，返回根节点
int merge(int x, int y) {
    if (!x || !y)
        return x + y;
    if (tr[x].rnd < tr[y].rnd) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    } else {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

// 插入v节点，以v为分割拆分成两个树x和y，将x,v,y三树合并
void insert(int v) {
    int x, y, z;
    split(root, v, x, y);
    newnode(z, v);
    root = merge(merge(x, z), y);
}

// 拆分出三颗树，x树内值小于v，y树内值等于v，z树内值大于v。
// y树左右子树合并成为新的y树，相当于将根删除，删除了一个v节点。
// 合并x, y, z三颗树。
void del(int v) {
    int x, y, z;
    split(root, v, x, z);
    split(x, v - 1, x, y);
    y = merge(tr[y].l, tr[y].r);
    root = merge(merge(x, y), z);
}

// 获取值的排名，以v-1进行分割，得到x树内值都小于等于v-1
// x树大小+1为v值的排名
int getrank(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int ans = tr[x].size + 1;
    root = merge(x, y);
    return ans;
}

// 获取排名为v的值，二分
int getval(int root, int v) {
    if (v == tr[tr[root].l].size + 1)
        return tr[root].val;
    else if (v <= tr[tr[root].l].size)
        return getval(tr[root].l, v);
    else
        return getval(tr[root].r, v - tr[tr[root].l].size - 1);
}

// v值前驱，拆分出x树，x树内值均小于v
// 找到x树内最大值
int getpre(int v) {
    int x, y, s, ans;
    split(root, v - 1, x, y);
    s = tr[x].size;
    ans = getval(x, s);
    root = merge(x, y);
    return ans;
}

// v值前驱，拆分出y树，x树内值均大于v
// 找到y树内最小值
int getnxt(int v) {
    int x, y, ans;
    split(root, v, x, y);
    ans = getval(y, 1);
    root = merge(x, y);
    return ans;
}

int main() {
    int n, op, v;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &op, &v);
        if (op == 1)
            insert(v);
        else if (op == 2)
            del(v);
        else if (op == 3)
            printf("%d\n", getrank(v));
        else if (op == 4)
            printf("%d\n", getval(root, v));
        else if (op == 5)
            printf("%d\n", getpre(v));
        else
            printf("%d\n", getnxt(v));
    }
    return 0;
}

P3391 【模板】文艺平衡树

您需要写一种数据结构，来维护一个有序数列。
其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。
第一行两个正整数 $n,m$，表示序列长度与操作个数。序列中第 $i$ 项初始为 $i$。
接下来 $m$ 行，每行两个正整数 $l,r$，表示翻转的区间。
输出一行 $n$ 个正整数，表示原始序列经过 $m$ 次变换后的结果。

对于splay可以将利用伸展操作将区间[l,r] 内的节点聚集在一颗子树上。而无旋treap也可以将区间聚集到一颗树上，然后打上懒标记。可以按照排名分裂，先将区间[1,n]分为[1, r], [r+1, n]，然后将[1, r]分为[1, l-1], [l, r] 。然后将[l,r]子树打上懒标记。

合并和分割操作遇到的每个节点都需要处理懒标记。

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
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 100005
#define MOD 998244353
using namespace std;

struct node {
    int l, r;  // 左右儿子
    int val;   // 树的权值
    int rnd;   // 堆的随机值
    int size;  // 子树大小
    int tag;   // 懒标记
} tr[N];
int root, idx;

void newnode(int& x, int v) {
    x = ++idx;
    tr[x].val = v;
    tr[x].rnd = rand();
    tr[x].size = 1;
    tr[x].tag = 0;
}

void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

void pushdown(int p) {
    if (tr[p].tag) {
        swap(tr[p].l, tr[p].r);
        tr[tr[p].l].tag ^= 1;
        tr[tr[p].r].tag ^= 1;
        tr[p].tag = 0;
    }
}

// 按照排名进行分裂，节点排名小于等于v划分到x，其余划分到y
void split(int p, int v, int& x, int& y) {
    if (!p) {
        x = y = 0;
        return;
    }
    pushdown(p);                 // 向下分裂过程中处理懒标记
    if (tr[tr[p].l].size < v) {  // 当前划分到x
        v -= tr[tr[p].l].size + 1;
        x = p;
        split(tr[x].r, v, tr[x].r, y);
    } else {
        y = p;
        split(tr[y].l, v, x, tr[y].l);
    }
    pushup(p);
}

// x树和y树合并成新树，返回根节点
int merge(int x, int y) {
    if (!x || !y)
        return x + y;
    if (tr[x].rnd < tr[y].rnd) {
        pushdown(x);
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    } else {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

// 插入v节点，以v为分割拆分成两个树x和y，将x,v,y三树合并
void insert(int v) {
    int x, y, z;
    split(root, v, x, y);
    newnode(z, v);
    root = merge(merge(x, z), y);
}

void dfs(int p) {
    if (!p)
        return;
    pushdown(p);
    dfs(tr[p].l);
    cout << tr[p].val << " ";
    dfs(tr[p].r);
}

void sol() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        insert(i);
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        int a, b, c;
        // 由于按照排名分裂的缘故，分裂有顺序要求
        split(root, r, a, c);   // 先分开[1 r] [r+1, n]
        split(a, l - 1, a, b);  // 再分开[1, l-1] [l, r]
        tr[b].tag ^= 1;
        root = merge(merge(a, b), c);
    }
    dfs(root);
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}