问题描述:
写一种数据结构，用来维护一个可重整数集合，需要提供以下操作（对于各个以往的历史版本）：
1. 插入 x ;
2. 删除 x（若有多个相同的数，应只删除一个，如果没有请忽略该操作）;
3. 查询的排名（排名定义为比当前数小的数的个数加 1）;
4. 查询排名为工的数 ;
5. 求工的前驱（前驱定义为小于工,且最大的数）；
6. 求工的后继（后继定义为大于工,且最小的数）。
和原本平衡树不同的是，每次的任何操作都是基于某一个历史版本，同时生成一个新的版本（操作 3 ~ 6 保持原版本无变化）。每个版本的编号即为操作的序号（版本 0 即为初始状态，空树）。
| 输入样例 | 输出样例 |
| 10 0 1 9 1 1 3 1 1 10 2 4 2 3 3 9 3 1 2 6 4 1 6 2 9 8 6 3 4 5 8 | 9 1 2 10 3 |
可持久化平衡树
#include <iostream>
#include <climits>
using namespace std;
const int N = 5e5 + 10;
int n, root[N], idx;
int x, y, z;
struct Node {
int l, r; //左右儿子
int key, val; //键值，随机优先值
int sz; //当前节点为根的子树节点数量
} tr[N * 50]; //存树
int newnode(int v) { //初始化新节点
int p = ++idx;
tr[p].key = v;
tr[p].val = rand();
tr[p].sz = 1;
return p; //返回新节点
}
#define pushup(u) tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1 //向上更新
void split(int p, int v, int &x, int &y) { //分裂
if (!p) { //到达叶子，递归返回
x = y = 0;
return;
}
if (tr[p].key <= v) { //本节点比 v 小，从右子树寻找 x
x = ++idx; //新开的点
tr[x] = tr[p]; //复制树 p
split(tr[x].r, v, tr[x].r, y); //分裂右子树
pushup(x);
} else { //本节点比 v 大 ，从左子树寻找 x
y = ++idx;
tr[y] = tr[p];
split(tr[y].l, v, x, tr[y].l);
pushup(y);
}
}
int merge(int x, int y) { //合并
if (!x || !y) return x ^ y; //x + y
if (tr[x].val < tr[y].val) { //左树优先级高于右树，x 节点是父节点
tr[x].r = merge(tr[x].r, y);
pushup(x);
return x;
} else { //y 是父节点
tr[y].l = merge(x, tr[y].l);
pushup(y);
return y;
}
}
void insert(int &root, int v) { //插入新节点
split(root, v, x, y); //按照 v 分裂
z = newnode(v); //新建节点 v
root = merge(merge(x, z), y); //v节点先合并左子树，再合并右子树
}
void remove(int &root, int v) { //删除节点
split(root, v, x, z); //分裂成三棵树，x，y，z
split(x, v - 1, x, y);
y = merge(tr[y].l, tr[y].r); //y树根节点去除
root = merge(merge(x, y), z); //三棵树重新合并
}
int get_rank(int &root, int v) { //查询 x 的排名
split(root, v - 1, x, y);
int res = tr[x].sz + 1; // 排名定义为比当前数小的数的个数
root = merge(x, y);
return res;
}
int get_key(int root, int rk) { //查询排名为 x 的数
if (rk <= tr[tr[root].l].sz) return get_key(tr[root].l, rk); //查询的 rt 在左子树中
else if (rk > tr[tr[root].l].sz + 1) //查询为 rt 在右子树中
return get_key(tr[root].r, rk - tr[tr[root].l].sz - 1);
else return tr[root].key; //返回键值
}
int get_prev(int &root, int v) { //小于 x，且最大的数
split(root, v - 1, x, y);
if (!x) return INT_MIN; //不存在
int res = get_key(x, tr[x].sz); //从左子树返回最后一个（最大）键值
root = merge(x, y);
return res;
}
int get_next(int &root, int v) { //大于 x，且最小的数
split(root, v, x, y);
if (!y) return INT_MAX; //不存在
int res = get_key(y, 1); //从右子树返回第一个（最小）键值
root = merge(x, y);
return res;
}
int main() {
scanf("%d", &n); //操作次数
for (int i = 1; i <= n; i++) {
int vi, op, x;
scanf("%d%d%d", &vi, &op, &x); //过去版本号、操作的序号、参与操作的数值
root[i] = root[vi]; //当前操作版本的根节点
if (op == 1) insert(root[i], x); //插入
else if (op == 2) remove(root[i], x); //删除
else if (op == 3) printf("%d\n", get_rank(root[i], x)); //查询 x 的排名
else if (op == 4) printf("%d\n", get_key(root[i], x)); //查询排名为 x 的数
else if (op == 5) printf("%d\n", get_prev(root[i], x)); //x 的前驱
else printf("%d\n", get_next(root[i], x)); //x 的后继
}
}
笔记：在普通平衡树的基础上加上了可持久化，这道题是上一篇的类似题，上一篇是用函数复制变化的节点，这是直接复制新的节点用在新的时间点上
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_46105170/article/details/126364514