笔记汇总

权值线段树是一个 树形桶，为取代树状数组迈出坚实一步。

它可以 快速计算出一段区间的数的出现次数。

与线段树区别不大（不是以出现次数作为节点），分开讲其实误导了很多人。

同样支持动态开点。

实现

每个节点维护的是当前节点维护的区间的数的 出现次数。

因为维护的区间是顺序的，所以可以用类似二分的方法查找序数关系。

即 k是第几大 和 第k大是几。

显而易见，它也是支持 可重集 的。

值得一提的是寻找 $p$前驱后继 的操作，

因为 $k$ 不明，所以要转换，

我们可以计算 $p$ 前面出现的数出现次数和后面的数出现个数，这恰好排除了 $p$，

从而达到目的。