You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1.8 KiB
1.8 KiB
普通平衡树【01trie写法】
主要就是trie的模板，这里对一些多出来的东西做一个解释
-
cnt[p]表示插入数的时候经过这个结点的次数，其实我们稍微转换一下，也就是结点p的子结点的个数。 -
rnk(x)表示的是小于x的数的个数 -
find_kth(k)表示第k个数
于是我们可以知道对于每条询问的表达方式了
1、insert(x, 1)
2、insert(x, -1)
3、rnk(x) + 1因为rnk(x)表示小于x的数的个数，加一就是x的位置了
4、find_kth(k) 查找第k个数字
5、find_kth(rnk(x))
名次k为小于x的数的个数，即k = rnk(x)，然后find_kth(k)就是小于x的最大值了。
6、类似5，我们做一个简单的推理，首先最后的表达式应该式类似于find_kth(rank(x))这样的形式的，然后需要查找的是大于x的最小值，也就是等价于先求小于等于x的数的个数，设为k然后求find_kth(k + 1)即可，也就是find_kth(rnk(x + 1) + 1)
代码难度比treap低了许多，写起来比较舒服，缺点是比较吃空间。
补充一下，因为输入有可能为负数，所以我们需要将所有数加上一个base，保证输入非负即可
如果还看不明白的可以试着手写一个trie来模拟一下，就会有所理解了。
已知最好写的平衡树，至少目前常数最小（测了大部分平衡树实现）
跑的比动态开点线段树什么的快多了
比Splay快1.5-2倍
唯一缺点是不能像Splay一样区间操作（不过能做这个的好像不多...）
还有内存占用较大，不过正常使用1e5-3e5几乎都是最大30M左右
主要是基于二进制分解的 Trie
同时满足二叉查找树，线段树和平衡树性质，具有高可扩展性