普通平衡树-trie树做法

  1. 普通平衡树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

上一篇:最大异或对(Trie 字典树)


下一篇:ADT: Trie Tree 字典树(附 Java 实现)