二叉搜索树

Definition

二叉搜索树（Binary Search Tree\text{Binary Search Tree}）是一种形状如二叉树的数据结构，用于快速查找和增加删除操作，它有如下几个特殊性质：

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

对于一个二叉搜索树，进行操作所花费的平均时间和这个二叉树的高度成正比。对于一个有 nn 个结点的二叉搜索树中，这些操作的最优时间复杂度为 O(log⁡n)O(\log n)，最坏为 O(n)O(n)​。

Define

对于一个二叉搜索树的每一个节点，都要存储以下几样东西：

  1. 左子树节点和右子树节点：l 和 r
  2. 这一个节点上存储的权值：val
  3. 表示这个节点权值出现次数的计数器：cnt
  4. 代表这个树上的大小（即子树和自己大小之和）：size
1
2
3
4
5
6
struct BST
{
    int l, r;       // 左右子树节点
    int val;        // 这一个节点上存储的权值
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];

与此同时，由于操作中需要不断插入新的数，因此还需要两个变量分别储存树的下标和当前的下标，我们用 root 和 idx 表示：

1
int root, idx;        // root表示这个树的根的下标，idx记录着当前的下标

Newnode

创建一个新的节点就是将这个节点全部初始化，同时返回原来的下标值：

1
2
3
4
5
6
int new_node(int k)                    // 创建新节点
{
    tr[idx].val = k;                // 将权值修改
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx;                     // 返回用过的下标（以后会用）
}

Pushup

像线段树一样，二叉搜索树同样也有需要维护的信息：每个子树的本身大小，有二叉树的性质可得出：

tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt\text{tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt} 

1
2
3
4
void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

Init

为了防止有时候询问的二叉搜索树为空，我们可以先在树中加入两个哨兵：-INF\text{-INF} 和 INF\text{INF}，在不断的插入中，他们会始终在树的左右两端，从而有效防止查询越界。

1
2
3
4
5
6
void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;          // 让根节点为1，右子树节点为2
    pushup(root);                   // 上传更新节点大小
}

Insert

根据二叉搜索树的性质可得，对于每个节点 uu 以及要插入的权值 kk，可以分为四种情况：

  1. u=ku = k 时，直接在该节点的计数变量上 cnt ++。
  2. u<ku < k 时，递归到该节点的右子树节点继续插入。
  3. u>ku > k 时，递归到该节点的左子树节点继续插入。
  4. u=0u = 0 时，则说明没有这个节点，直接利用 idx 创建一个。

tips\bold tips：在递归完之后要 pushup 一遍，从而维护每个子树的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k) insert(tr[u].l, k);  // 向左递归
            else insert(tr[u].r, k);                // 向右递归
        }
    }
    pushup(u);                              // 上传信息
}

Remove

原理和插入相似，不多赘述，一共五种情况：

  1. u=ku = k 时，直接在该节点的计数变量上 cnt --。
  2. uu 节点为叶子节点时，直接 u = 0。
  3. u<ku < k 时，递归到该节点的右子树节点继续删除。
  4. u>ku > k 时，递归到该节点的左子树节点继续删除。
  5. u=0u = 0 时，则说明没有这个节点，直接 return 掉 。

tips\bold tips：在递归完之后要 pushup 一遍，从而维护每个子树的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r) del(tr[u].r, k);  // 如果有右子树，向右递归
                else del(tr[u].l, k);           // 否则向左递归
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

FindPrev

一个数 xx 的前驱被定义为小于 xx 的最大的数。

对于一个节点 uu 的权值以及权值 kk，它的查询分为以下三种情况：

  1. u=0u = 0 时，此时说明找到了最左端，应当 return -INF。
  2. u≥ku \ge k 时，说明 $k $的前驱还可能在当前节点的左子树，向左递归。
  3. 其余的情况则说明 u≤ku \le k，此时分为两种情况，一是前驱就是 uu，二是前驱在右子树当中，因此在两者中取 max⁡\max。
1
2
3
4
5
6
int get_prev(int u, int k)            // 找前驱
{
    if (u == 0) return -INF;        // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);        // 否则在两者之中取最大值
}

FindNext

一个数 xx 的后驱被定义为大于 xx 的最小的数。

原理同上

1
2
3
4
5
6
int get_next(int u, int k)            // 找后驱
{
    if (u == 0) return INF;         // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);        // 否则在两者之中取最小值
}

Get_Val_by_Rank

排名定义为比当前数小的数的个数 +1+1。若有多个相同的数，应输出最小的排名。

对于一个节点 uu 以及 rankrank 值，可以分为以下四种情况：

  1. tr[u].val=0\text{tr[u].val} = 0 时，说明这个权值无限大，返回 INF\text{INF}。
  2. tr[tr[u].l].size ≥rank\text{tr[tr[u].l].size } \ge \text{rank}，说明权值在左子树里面，向左递归。
  3. tr[tr[u].l].size + tr[u].cnt≥rank\text{tr[tr[u].l].size + tr[u].cnt} \ge \text{rank}，由于上面的限制条件，说明该节点权值即为答案。
  4. 否则向右进行递归，并且注意右子树中的 $rank $ 值是相对的。
1
2
3
4
5
6
7
int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF;     // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);    // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;             // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);   // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

Get_Rank_By_Val

原理和上面反过来差不多

1
2
3
4
5
6
7
int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;       // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;        // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);  // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);  // 否则应该向右递归，并且加上左子树和节点的大小之和
}

Template Code

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>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// #define int long long

const int N = 1e5 + 9;
const int INF = 2147483647;

struct BST
{
    int l, r;    // 左右子树节点
    int val;    // 这一个节点上存储的权值
    int cnt, size;    // 节点权值出现次数的计数器和这个树的大小
}tr[N];
int root, idx;    // root表示这个树的根的下标，idx记录着当前的下标

void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

int new_node(int k)    // 创建新节点
{
    tr[++ idx].val = k;    // 将权值修改
    tr[idx].size = tr[idx].cnt = 1;    // 默认的子树的大小以及出现的次数肯定为1
    return idx;    // 返回用过的下标（以后会用）
}

void build()
{
    new_node(-INF), new_node(INF);    // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;    // 让根节点为1，右子树节点为2
    pushup(root);    // 上传更新节点大小
}

void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);    // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;    // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k) insert(tr[u].l, k);    // 向左递归
            else insert(tr[u].r, k);    // 向右递归
        }
    }
    pushup(u);    // 上传信息
}

void del(int &u, int k)
{
    if (u == 0) return;    // 如果节点为0，直接return
    if (tr[u].val == k)    // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;    // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)    // 不是叶子节点时
            {
                if (!tr[u].r) del(tr[u].r, k);    // 如果有右子树，向右递归
                else del(tr[u].l, k);    // 否则向左递归
            }
            else u = 0;    // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);    // 向右递归
    pushup(u);    // 上传信息
}

int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;    // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;        // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);  // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);  // 否则应该向右递归，并且加上左子树和节点的大小之和
}

int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF;     // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);
        // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;
        // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt); 
        // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

int get_prev(int u, int k)    // 找前驱
{
    if (u == 0) return -INF;    // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);    // 否则在两者之中取最大值
}

int get_next(int u, int k)    // 找后驱
{
    if (u == 0) return INF;    // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);    // 否则在两者之中取最小值
}

signed main()
{
    build();
    int n; cin >> n;
    while (n --)
    {
        int op, k; cin >> op >> k;
        if (op == 5) insert(root, k);
        else if (op == 1)
        {
            insert(root, k);
            cout << get_rank_by_val(root, k) - 1 << '\n';
            del(root, k);
        }
        else if (op == 2) cout << get_val_by_rank(root, k + 1) << '\n';
        else if (op == 3) cout << get_prev(root, k) << '\n';
        else cout << get_next(root, k) << '\n';
    }
    return 0;
}

平衡树

P3369 【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态

P6136 【模板】普通平衡树（数据加强版） - 洛谷 | 计算机科学教育新生态

P3391 【模板】文艺平衡树 - 洛谷 | 计算机科学教育新生态

Definition

平衡树简介

使用搜索树的目的之一是 缩短插入、删除、修改和查找（插入、删除、修改都包括查找操作）节点的时间。 关于查找效率，如果一棵树的高度为 hh，在最坏的情况，查找一个关键字需要对比 hh 次，查找时间复杂度（也为平均查找长度 ASL，Average Search Length\text{ASL，Average Search Length}）不超过 O(h)O(h)。一棵理想的二叉搜索树所有操作的时间可以缩短到 O(log⁡n)O(\log n)（nn 是节点总数）。 然而 O(h)O(h) 的时间复杂度仅为理想情况。在最坏情况下，搜索树有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树，那么它的性质就和链表一样，所有操作（增删改查）的时间是 O(n)O(n)。 可以发现操作的复杂度与树的高度 hh 有关。由此引出了平衡树，通过一定操作维持树的高度（平衡性）来降低操作的复杂度。

一个平衡树有如下几个定义：

  1. 它是一个二叉搜索树
  2. 对于任意一个节点的子树，每一个节点的左子树和右子树的高度差最多为 11。

Rotate Treap

Description

Treap\text{Treap}（树堆）是一种 弱平衡 的 二叉搜索树。它同时符合二叉搜索树和堆的性质，名字也因此为 tree\text{tree}（树）和 heap\text{heap}（堆）的组合。

其中对于堆的性质是：

  • 子节点值（priority\textit{priority}）比父节点大或小（取决于是小根堆还是大根堆）。

https://oi-wiki.org/ds/images/treap-treap-example.svg

Zig / Zag

旋转 Treap\text{Treap}通过 左旋 和 右旋 的方式维护平衡树的平衡，通过调整堆的优先级从而达到平衡操作。

旋转操作的含义：

  • 在不影响搜索树性质的前提下，把和旋转方向相反的子树变成根节点（如左旋，就是把右子树变成根节点）
  • 不影响性质，并且在旋转过后，跟旋转方向相同的子节点变成了原来的根节点（如左旋，旋转完之后的左子节点是旋转前的根节点）

https://oi-wiki.org/ds/images/treap-rotate.svg

代码思路需要慢慢悟出来

1
2
3
4
5
6
7
8
9
10
11
12
13
void zig(int &u)                            // 右旋
{
    int v = tr[u].l;                        // v是节点u的左子节点
    tr[u].l = tr[v].r, tr[v].r = u, u = v;  // 依次更新节点
    pushup(tr[u].r), pushup(u);             // 上传标记
}

void zag(int &u)                            // 左旋
{
    int v = tr[u].r;                        // v是节点u的右子节点
    tr[u].r = tr[v].l, tr[v].l = u, u = v;  // 依次更新节点
    pushup(tr[u].l), pushup(u);             // 上传标记
}

Insert

和二叉搜索树差不多，只不过要在插入的过程中维护好堆的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k)
            {
                insert(tr[u].l, k);     // 向左递归
                if (tr[tr[u].l].key > tr[u].key) zig(u); // 如果不满足堆的性质，右旋
            }
            else
            {
                insert(tr[u].r, k);     // 向右递归
                if (tr[tr[u].r].key < tr[u].key) zag(u); // 如果不满足堆的性质，左旋
            }
        }
    }
    pushup(u);                              // 上传信息
}

Remove

同样维护好堆的性质

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
void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r || tr[tr[u].l].key > tr[tr[u].r].key) // 有右子树或者左子树的key大于右子树的key
                {
                    zig(u);             // 右旋
                    del(tr[u].r, k);    // 向右递归
                }
                else 
                {
                    zag(u);             // 左旋
                    del(tr[u].l, k);    // 否则向左递归
                }
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

Template Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// #define int long long

const int N = 1e5 + 9;
const int INF = 0x3f3f3f3f;

struct BST
{
    int l, r;   // 左右子树节点
    int val, key;   // val: 这一个节点上存储的权值  key: 随机数以满足堆的性质
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];
int root, idx;  // root表示这个树的根的下标，idx记录着当前的下标

void pushup(int u)  // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

int new_node(int k) // 创建新节点
{
    tr[++ idx].val = k; // 将权值修改
    tr[idx].key = rand();   // 给key赋予一个随机数
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx; // 返回用过的下标（以后会用）
}

void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;  // 让根节点为1，右子树节点为2
    pushup(root);   // 上传更新节点大小
}

void zig(int &u)    // 右旋
{
    int v = tr[u].l;    // v是节点u的左子节点
    tr[u].l = tr[v].r, tr[v].r = u, u = v;  // 依次更新节点
    pushup(tr[u].r), pushup(u); // 上传标记
}

void zag(int &u)    // 左旋
{
    int v = tr[u].r;    // v是节点u的右子节点
    tr[u].r = tr[v].l, tr[v].l = u, u = v;  // 依次更新节点
    pushup(tr[u].l), pushup(u); // 上传标记
}

void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);    // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k)
            {
                insert(tr[u].l, k); // 向左递归
                if (tr[tr[u].l].key > tr[u].key) zig(u);    // 如果不满足堆的性质，右旋
            }
            else
            {
                insert(tr[u].r, k); // 向右递归
                if (tr[tr[u].r].key < tr[u].key) zag(u);    // 如果不满足堆的性质，左旋
            }
        }
    }
    pushup(u);  // 上传信息
}

void del(int &u, int k)
{
    if (u == 0) return ;    // 如果节点为0，直接return
    if (tr[u].val == k) // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;    // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r) // 不是叶子节点时
            {
                if (!tr[u].r || tr[tr[u].l].key > tr[tr[u].r].key)  // 有右子树或者左子树的key大于右子树的key
                {
                    zig(u); // 右旋
                    del(tr[u].r, k);    // 向右递归
                }
                else 
                {
                    zag(u); // 左旋
                    del(tr[u].l, k);    // 否则向左递归
                }
            }
            else u = 0; // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);   // 向右递归
    pushup(u);  // 上传信息
}

int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;   // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;
         // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);
        // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);
        // 否则应该向右递归，并且加上左子树和节点的大小之和
}

int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF; // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);
        // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;
        // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);
        // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

int get_prev(int u, int k)  // 找前驱
{
    if (u == 0) return -INF;    // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);    // 否则在两者之中取最大值
}

int get_next(int u, int k)  // 找后驱
{
    if (u == 0) return INF; // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);    // 否则在两者之中取最小值
}

signed main()
{
    build();
    int n; cin >> n;
    while (n --)
    {
        int op, k; cin >> op >> k;
        if (op == 1) insert(root, k);
        else if (op == 2) del(root, k);
        else if (op == 3)
        {
            insert(root, k);
            cout << get_rank_by_val(root, k) - 1<< '\n';
            del(root, k);
        }
        else if (op == 4) cout << get_val_by_rank(root, k + 1) << '\n';
        else if (op == 5) cout << get_prev(root, k) << '\n';
        else cout << get_next(root, k) << '\n';
    }
    return 0;
}

FHQ Treap

以上方式实现的平衡树是比较繁琐难记的，而且常熟本身就很大，在学会了线段树的合并和分类之后，我们就可以维护一颗权值线段树，通过不断地分裂与合并从而维护序列地有序和平衡。

具体地，如果我们要在第 kk 个位置（或者特定权值同理）插入一个数，仅仅需要将这颗树分裂为两部分，将这个权值放在中间依次合并这三部分。如果要删除，我们可以分割出前 kk 个权值的线段树，再将这棵树的前 k−1k - 1 个分裂出来，与后者合并即可。由于平衡树只需要维护子树大小，所以更新是非常方便的。

它保留了旋转 Treap 的重要做法，即随机赋权值，从而保持树的唯一性和平衡性（期望为 log⁡n\log n​ 高度）。

Init

1
2
3
4
5
6
7
8
9
10
11
12
int Root, Lfs, Rfs, Tfs, idx;
    // 每次操作后只有一颗树，这棵树的根存储在 Root 中，Lfs Rfs Tfs 均为临时变量存储操作时的根。

struct Node 
{
    int ls, rs, sz, val, pri;
    Node(int _val = 0, int _sz = 0) : ls(0), rs(0), sz(_sz), val(_val), pri(rnd()) {}
} tr[N];

inline int newnode(int val) { return tr[++ idx] = Node(val, 1), idx; }

inline void pushup(int u) { tr[u].sz = tr[lc].sz + tr[rc].sz + 1; }

Split

1
2
3
4
5
6
7
8
9
void split(int cur, int &x, int &y, int k)    // x, y 存储分裂到当前节点时两颗树的根，便于分裂后的操作
{
    if (!cur) return x = y = 0, void();
    if (tr[cur].val <= k)     // 当前权值小于等于 k 时，向子树的右侧分裂
        x = cur, split(tr[cur].rs, tr[cur].rs, y, k);
    else    // 否则向左侧分裂
        y = cur, split(tr[cur].ls, x, tr[cur].ls, k);
    pushup(cur);
}    // 所示为按照权值分裂的代码，k 始终不变
1
2
3
4
5
6
7
8
9
10
void split(int cur, int val, int &x, int &y)
{
    if (!cur) return x = y = 0, void();
    pushdown(cur);
    if (val <= tr[tr[cur].ls].sz)
        y = cur, split(tr[cur].ls, val, x, tr[cur].ls);
    else
        x = cur, split(tr[cur].rs, val - tr[tr[cur].ls].sz - 1, tr[cur].rs, y);
    pushup(cur);
}    // 所示为按照下标分裂的，k 在遍历右子树时减去偏移量

Merge

顾名思义，每次传入两颗分裂树后的根，并且权值小的树在前，大的树在后。不断根据初始化时的随机数调整树使其满足堆的性质。由于左右子树分别有序，所以合并必然也有序（这里是保证平衡的关节步骤）。

所示代码用大根堆维护，即 pripri 值大的为根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int merge(int x, int y)    // 传入两棵树的根节点，返回合并后树的根
{
    if (!x || !y) return x | y;
    if (tr[x].pri >= tr[y].pri)    // x 的 pri 更大，x 为根
    {
        tr[x].rs = merge(tr[x].rs, y);    // 递归合并右子树，已保证左子树合法
        return pushup(x), x;    // 记得要上传更新
    }
    else
    {
        tr[y].ls = merge(x, tr[y].ls);    // 递归合并左子树，已保证右子树合法
        return pushup(y), y;
    }
}

Insert

1
2
3
4
5
inline void insert(int val)
{
    split(Root, Lfs, Rfs, val);    // 以 val 为分界分为 <= val 和 > val 的两棵树，根为 x 和 y
    Root = merge(Lfs, merge(newnode(val), Rfs)); // 三棵树依次合并
}

Remove

1
2
3
4
5
6
7
8
inline void remove(int val)
{
    split(Root, Lfs, Rfs, val), split(Lfs, Lfs, Tfs, val - 1);
        // 分裂为 < val, = val 和 > val 的三棵树，分别为 Lfs, Tfs, Rfs
    Tfs = merge(tr[Tfs].ls, tr[Tfs].rs), Root = merge(merge(Lfs, Tfs), Rfs);
        // merge 一遍 Tfs 是因为题目要求相同权值仅删去一个，merge 后可以直接去掉根上的值
       // Root = merge(Lfs, Rfs); 如果要求全删
}

Get_Rank_By_Val

1
2
3
4
5
6
7
inline int get_rank_by_val(int val)
{
    split(Root, Lfs, Rfs, val - 1);
    int res = tr[Lfs].sz + 1;    // < val 的子树大小 + 1 即为 val 的 rank 值
    Root = merge(Lfs, Rfs);    // ！
    return res;
}

Get_Val_By_Rank

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline int GetVal(int rk)
{
    int cur = Root;
    while (cur)
    {
        if (rk <= tr[tr[cur].ls].sz) cur = tr[cur].ls;
            // 所求的 rank 值不大于左子树大小，向左递归
        else if (rk == tr[tr[cur].ls].sz + 1) return tr[cur].val;
            // 刚好为当且节点的 rank 值，返回
        else rk -= tr[tr[cur].ls].sz + 1, cur = tr[cur].rs;
            // 否则向右递归，并减去偏移量
    }
    return tr[cur].val;
}

Get_Pre / Get_Suf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline int GetPre(int val)
{
    split(Root, Lfs, Rfs, val - 1), Tfs = Lfs;
    while (tr[Tfs].rs) Tfs = tr[Tfs].rs;    // < val 的子树最右边的节点为所求
    Root = merge(Lfs, Rfs);
    return tr[Tfs].val;
}

inline int GetSuf(int val)
{
    split(Root, Lfs, Rfs, val), Tfs = Rfs;
    while (tr[Tfs].ls) Tfs = tr[Tfs].ls;    // > val 的子树最左边的节点为所求
    Root = merge(Lfs, Rfs);
    return tr[Tfs].val;
}

Template Code

数组版本（细节少，代码量大，难调）

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
int Root, Lfs, Rfs, Tfs, idx;

struct FHQTreap
{
    #define lc tr[u].ls
    #define rc tr[u].rs

    struct Node 
    {
        int ls, rs, sz, val, pri;
        Node(int _val = 0, int _sz = 0) : ls(0), rs(0), sz(_sz), val(_val), pri(rnd()) {}
    } tr[N];

    inline int newnode(int val) { return tr[++ idx] = Node(val, 1), idx; }

    inline void pushup(int u) { tr[u].sz = tr[lc].sz + tr[rc].sz + 1; }

    void split(int cur, int &x, int &y, int k)
    {
        if (!cur) return x = y = 0, void();
        if (tr[cur].val <= k) 
            x = cur, split(tr[cur].rs, tr[cur].rs, y, k);
        else
            y = cur, split(tr[cur].ls, x, tr[cur].ls, k);
        pushup(cur);
    }

    int merge(int x, int y)
    {
        if (!x || !y) return x | y;
        if (tr[x].pri >= tr[y].pri)
        {
            tr[x].rs = merge(tr[x].rs, y);
            return pushup(x), x;
        }
        else
        {
            tr[y].ls = merge(x, tr[y].ls);
            return pushup(y), y;
        }
    }

    inline void insert(int val)
    {
        split(Root, Lfs, Rfs, val);
        Root = merge(Lfs, merge(newnode(val), Rfs));
    }

    inline void remove(int val)
    {
        split(Root, Lfs, Rfs, val), split(Lfs, Lfs, Tfs, val - 1);
        Root = merge(Lfs, Rfs);
    }

    inline int GetRank(int val)
    {
        split(Root, Lfs, Rfs, val - 1);
        int res = tr[Lfs].sz + 1;
        Root = merge(Lfs, Rfs);
        return res;
    }

    inline int GetVal(int rk)
    {
        int cur = Root;
        while (cur)
        {
            if (rk <= tr[tr[cur].ls].sz) cur = tr[cur].ls;
            else if (rk == tr[tr[cur].ls].sz + 1) return tr[cur].val;
            else rk -= tr[tr[cur].ls].sz + 1, cur = tr[cur].rs;
        }
        return tr[cur].val;
    }

    inline int GetPre(int val)
    {
        split(Root, Lfs, Rfs, val - 1), Tfs = Lfs;
        while (tr[Tfs].rs) Tfs = tr[Tfs].rs;
        Root = merge(Lfs, Rfs);
        return tr[Tfs].val;
    }

    inline int GetSuf(int val)
    {
        split(Root, Lfs, Rfs, val), Tfs = Rfs;
        while (tr[Tfs].ls) Tfs = tr[Tfs].ls;
        Root = merge(Lfs, Rfs);
        return tr[Tfs].val;
    }
} BST;

指针版（容易 RE，码量少，优雅）

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
struct FHQTreap
{
    struct Node
    {
        int val, sz, pri;
        Node *ls, *rs;
        Node(int _val) : val(_val), pri(rnd()), sz(1), ls(NULL), rs(NULL) {}
    } *Root = NULL, *Lfs = NULL, *Rfs = NULL, *Tfs = NULL;

    inline int size(Node* u) { return u ? u -> sz : 0; }

    inline void pushup(Node *u) { if (!u) return; u -> sz = size(u -> ls) + size(u -> rs) + 1; }

    void split(Node *u, Node *&x, Node *&y, int k)
    {
        if (!u) return void(x = y = NULL);
        if (u -> val <= k)
            x = u, split(u -> rs, u -> rs, y, k);
        else
            y = u, split(u -> ls, x, u -> ls, k);
        pushup(u);
    }

    Node* merge(Node *x, Node *y)
    {
        if (!x || !y) return x ? x : y;
        if (x -> pri >= y -> pri)
            return x -> rs = merge(x -> rs, y), pushup(x), x;
        else
            return y -> ls = merge(x, y -> ls), pushup(y), y;
    }

    inline void insert(Node *&root, int val)
    {
        split(root, Lfs, Rfs, val);
        root = merge(Lfs, merge(new Node(val), Rfs));
    }

    inline void remove(Node *&root, int val)
    {
        split(root, Lfs, Rfs, val), split(Lfs, Lfs, Tfs, val - 1);
        root = merge(Lfs, merge(merge(Tfs -> ls, Tfs -> rs), Rfs));
        delete(Tfs);
    }

    int getrank(Node *root, int val)
    {
        split(root, Lfs, Rfs, val - 1);
        int res = size(Lfs) + 1;
        root = merge(Lfs, Rfs);
        return res;
    }

    int getval(Node *root, int rank)
    {
        Node *cur = root;
        while (cur)
        {
            if (size(cur -> ls) >= rank) cur = cur -> ls;
            else if (size(cur -> ls) + 1 == rank) return cur -> val;
            else rank -= size(cur -> ls) + 1, cur = cur -> rs;
        }
        return -1;
    }

    int getprev(Node *root, int val)
    {
        split(root, Lfs, Rfs, val - 1);
        Tfs = Lfs;
        while (Tfs && Tfs -> rs) Tfs = Tfs -> rs;
        root = merge(Lfs, Rfs);
        return Tfs ? Tfs -> val : -1;
    }

    int getnext(Node *root, int val)
    {
        split(root, Lfs, Rfs, val);
        Tfs = Rfs;
        while (Tfs && Tfs -> ls) Tfs = Tfs -> ls;
        root = merge(Lfs, Rfs);
        return Tfs ? Tfs -> val : -1;
    }
} BST;

可持久化平衡树

和线段树一样，平衡树（部分）同样可以实现可持久化的功能。

FHQ Treap

FHQ Treap 的结构与线段树相似，同时通过主要的两个操作可以十分方便地实现可持久化。

主要的变化在于每次 split 和 merge 的时候都要复制当前的节点。

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
struct SustainableFHQTreap
{
    struct Node
    {
        int val, sz, pri;
        Node *ls, *rs;
        Node(int _val = 0) : val(_val), pri(rnd()), sz(1), ls(NULL), rs(NULL) {}
        Node(Node *u) { *this = *u; }
    } *Lfs = NULL, *Rfs = NULL, *Tfs = NULL;

    inline int size(Node* u) { return u ? u -> sz : 0; }

    inline void pushup(Node *u) { u -> sz = size(u -> ls) + size(u -> rs) + 1; }

    inline Node* clone(Node *u) { return !u ? NULL : new Node(u); }

    void split(Node *u, Node *&x, Node *&y, int k)
    {
        if (!u) return void(x = y = NULL);
        u = clone(u);
        if (u -> val <= k)
            x = u, split(u -> rs, u -> rs, y, k);
        else
            y = u, split(u -> ls, x, u -> ls, k);
        pushup(u);
    }

    Node* merge(Node *x, Node *y)
    {
        if (!x || !y) return x ? x : y;
        if (x -> pri >= y -> pri)
        {
            x = clone(x), x -> rs = merge(x -> rs, y);
            return pushup(x), x;
        }
        else
        {
            y = clone(y), y -> ls = merge(x, y -> ls);
            return pushup(y), y;
        }
        return NULL;
    }

    inline void insert(Node *&root, int val)
    {
        split(root, Lfs, Rfs, val);
        Node *newnode = new Node(val);
        root = merge(Lfs, merge(newnode, Rfs));
    }

    inline void remove(Node *&root, int val)
    {
        split(root, Lfs, Rfs, val), split(Lfs, Lfs, Tfs, val - 1);
        if (Tfs) root = merge(Lfs, merge(merge(Tfs -> ls, Tfs -> rs), Rfs));
        else root = merge(Lfs, Rfs);
        // delete(Tfs);    手动分配了内存就不能 delete 了
    }

    int getrank(Node *root, int val)
    {
        split(root, Lfs, Rfs, val - 1);
        int res = size(Lfs) + 1;
        root = merge(Lfs, Rfs);
        return res;
    }

    int getval(Node *root, int rank)
    {
        Node *cur = root;
        while (cur)
        {
            if (size(cur -> ls) >= rank) cur = cur -> ls;
            else if (size(cur -> ls) + 1 == rank) return cur -> val;
            else rank -= size(cur -> ls) + 1, cur = cur -> rs;
        }
        return -1;
    }

    int getprev(Node *root, int val)
    {
        split(root, Lfs, Rfs, val - 1);
        Tfs = Lfs;
        while (Tfs && Tfs -> rs) Tfs = Tfs -> rs;
        root = merge(Lfs, Rfs);
        return Tfs ? Tfs -> val : -INF;
    }

    int getnext(Node *root, int val)
    {
        split(root, Lfs, Rfs, val);
        Tfs = Rfs;
        while (Tfs && Tfs -> ls) Tfs = Tfs -> ls;
        root = merge(Lfs, Rfs);
        return Tfs ? Tfs -> val : -INF;
    }

} BST;
SustainableFHQTreap::Node *root[N];

可持久化文艺平衡树（区间反转）

需要注意的点是 pushdown(u) 当中也要新建克隆的节点。

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
struct FHQTreap
{
    struct Node
    {
        int sum, val, sz, pri, rev;
        Node *ls, *rs;
        Node(int _val = 0, int _sz = 1) { sum = val = _val, rev = 0, sz = _sz, pri = rnd(), ls = rs = NULL; }
        Node(Node* u) { *this = *u; }
    } *Lfs = NULL, *Rfs = NULL, *Tfs = NULL, EMP;

    inline Node* get(Node *u) { return u ? u : &EMP; }

    inline int size(Node *u) { return u ? u -> sz : 0; }

    inline Node* clone(Node *u) { return u ? new Node(u) : NULL; }

    inline void pushup(Node *u)
    {
        u -> sum = get(u -> ls) -> sum + get(u -> rs) -> sum + u -> val;
        u -> sz = size(u -> ls) + size(u -> rs) + 1; 
    }

    inline void pushdown(Node *u)
    {
        if (!u -> rev) return;
        swap(u -> ls, u -> rs);
        if (u -> ls) u -> ls = clone(u -> ls), u -> ls -> rev ^= 1;
        if (u -> rs) u -> rs = clone(u -> rs), u -> rs -> rev ^= 1;
        u -> rev ^= 1;
    }

    void split(Node *u, Node *&x, Node *&y, int k)
    {
        if (!u) return void(x = y = NULL);
        pushdown(u);
        u = clone(u);
        if (k <= size(u -> ls))
            y = u, split(u -> ls, x, u -> ls, k);
        else
            x = u, split(u -> rs, u -> rs, y, k - size(u -> ls) - 1);
        pushup(u);
    }

    Node* merge(Node *x, Node *y)
    {
        if (!x || !y) return x ? x : y;
        pushdown(x), pushdown(y);
        if (x -> pri >= y -> pri)
        {
            x = clone(x), x -> rs = merge(x -> rs, y);
            return pushup(x), x;
        }
        else
        {
            y = clone(y), y -> ls = merge(x, y -> ls);
            return pushup(y), y;
        }
    }

    inline void insert(Node *&root, int x, int k)
    {
        split(root, Lfs, Rfs, x);
        root = merge(Lfs, merge(new Node(k), Rfs));
    }
    
    inline void remove(Node *&root, int x)
    {
        split(root, Lfs, Rfs, x), split(Lfs, Lfs, Tfs, x - 1);
        root = merge(Lfs, Rfs);
        delete(Tfs);
    }

    inline void reverse(Node *&root, int x, int y)
    {
        split(root, Lfs, Rfs, y), split(Lfs, Lfs, Tfs, x - 1);
        if (Tfs) Tfs -> rev ^= 1;
        root = merge(Lfs, merge(Tfs, Rfs));
    }

    inline int query(Node *&root, int x, int y)
    {
        split(root, Lfs, Rfs, y), split(Lfs, Lfs, Tfs, x - 1);
        int res = Tfs ? Tfs -> sum : 0;
        root = merge(Lfs, merge(Tfs, Rfs));
        return res;
    }
} BST;
FHQTreap::Node *root[N];

Reference

二叉搜索树 & 平衡树 - OI Wiki

P3369 【模板】普通平衡树 - 洛谷

P6136 【模板】普通平衡树（数据加强版） - 洛谷

Treap - OI Wiki