平衡树套平衡树!

· · 算法·理论

例题1

考虑外侧维护一个关于值的平衡树，这里只能使用 这个平衡树 或者 01-trie，因为这两种平衡树的每次操作不会改变树的结构，只会导致 O(\log v) 个节点的信息发生 O(1)的变化，而传统平衡树会导致信息发生巨大的变化。

这个平衡树的每个节点维护一个 等价类平衡树，表示只考虑这些值的每个点的集合大小。

然后我们在平衡树上二分，每次二分有 O(\log n) 的代价，就是一次查询区间和，而 这个平衡树 的高度是 O(\log v) 的，总复杂度是 O(q \log n \log v)的。

这个的优势是空间是 O(n \log v) 的，而且它跑得比传统的树套树还快不少，而且支持一些关于值的操作，感觉主要是因为这个平衡树本身常数非常优秀，虽然略慢于整体二分，但它在线啊！

然后这个外层关于值，内层关于区间的想法有非常大的用，可能可以很好支持一些传统树套树难以解决的问题。

提交记录2.15s。

例题2

树套树板子题，做法参考上面的，区别就是内层不需要使用等价类平衡树了。

提交记录

不知道为啥，这个跑的就非常的慢。

没有例题

考虑我们使用上述结构套一个 top tree，然后我们就可以实现动态树链 kth 之类的操作了，因为你只能建一个虚树，所以你可能需要再维护一个 set，以帮助你动态建虚树，如果这个树本身是动态的，你就可以跳了。

这个东西肉眼可见没人想写。