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
同时满足二叉查找树，线段树和平衡树性质，具有高可扩展性