253. 普通平衡树https://www.acwing.com/problem/content/255/

#include <iostream>

using namespace std;

const int N = 3e6 + 10;
struct Trie {
	int son[N][2], root = 1, idx = 1, base = 1e7;
	int sum[N];
	void insert (int x, int t) {
		int p = root;
		x += base;
		for (int i = 31; ~i; i --) {
			int c = x >> i & 1;
			if (!son[p][c]) son[p][c] = ++ idx;
			 p = son[p][c];
			sum[p] += t;
		}
	}
	int rank (int x) {
		int p = root;
		x += base;
		int res = 0;
		for (int i = 31; ~i; i--) {
			int c = x >> i & 1;
			if (c) res += sum[son[p][0]];
			p = son[p][c];
		}
		return res;
	}
	int key (int x) {
		int p = root;
		int res = 0;
		for (int i = 31; ~i; i --) {
			int c = x >> i & 1;
			if (x > sum[son[p][0]]) x -= sum[son[p][0]], res += 1 << i, p = son[p][1];
			else p = son[p][0];
		}
		return res - base;
	}
}trie;
int main () {
	int n;
	cin >> n;
	while (n --) {
		int op, x;
		cin >> op >> x;
		if (op ==1) {
			trie.insert (x, 1);
		}
		else if(op == 2) {
			trie.insert (x, -1);
		}
		else if (op == 3) {
			cout << trie.rank (x) + 1 << endl;
		}
		else if (op == 4) {
			cout << trie.key (x) << endl;
		}
		else if (op == 5) {
			cout << trie.key(trie.rank(x)) << endl;
		}
		else
			cout << trie.key(trie.rank(x + 1) + 1) << endl;
	}
	return 0;
}

1、如何运用tire树？
2、还需要记录什么量？
需要记录一个结点的子节点，一个节点的子节点数量是如何定义的？表示经过这个点的次数。就是共用这个点的数的数量
sum[p] += t;
3、如何根据排名求数值？
key(x)
4、如何根据数值求排名？
需要传入几个参数？分别是什么参数？一个参数，参数是数值，rank (x);
步骤是什么？需要什么变量？需要一个变量c用来接受x>>i & 1, res 用来存储小于x的个数。res如何使用？在什么条件
下使用？如果c为1，那么就更新res += sum[nex[p][0]],因为nex[p][0]方向一定小于x，所以可以加上这个方向
小于nex[p][0]的子节点数量，表示那边有多少个数。 因此某个位置始终满足左边是小于x，右边是大于等于x，相当于二分
的搜索过程，最终搜到一个等于x的值。p有什么用？p用来存储父节点，每次循环末尾跟新p;

5、如何插入一个数？
insert(x, 1)
6、如何删除一个数？
insert (x, -1)这里会更新sum[p]的值，如果经过这个点，就会减去一个数。
7、如何求后继？
key(rand(x + 1))返回最后一个小于等于x的数的值，所以key(rank(x+1) + 1)返回最后小于等于的数的后一个值
8、如何求前驱？
k