? ! 无需旋转和合并的平衡树？!

jsq1004 · 2026-10-16 11:02:09 · 算法·理论

这个东西比替罪羊的优势是支持可持久化。

这个东西跟先序遍历平衡树一样，做不了区间翻转。

事实上，它更像权值线段树。

这个东西的每个节点需要像线段树一样维护一个值域上的区间，还要维护两个值，左中值和右中值，分别表示左边跟 mid 最接近的和右边跟 mid 最接近的。

插入时，如果发现新插入的值比目前维护的左中值或右中值更靠近 mid，那么就 swap 一下，然后往左右儿子递归。

如果现在这里没有点，就新建一个，根据值在左边还是在右边决定是左中值还是右中值。

删除可以考虑维护 cnt ，然后找到对应的点，减一下 cnt，不过应该是有更真的实现的，比如把左边的最大值拿上来充当新的左中值，但是如果不维护 cnt 的话，同一个值插入很多次会出问题，需要一些手法，所以我没写。

kth 之类的操作也是好做的，跟其他平衡树差不多，不过因为它在中间有两个值，所以会难写一点。

复杂度显然是对的，因为这个东西结构就是类似于线段树的，常熟也不大，跑得跟红黑树差不了多少，如果实现精细应该可以更快。

这个东西的空间是严格 n 的，树高是严格 \log v 且随机数据卡不满的。

不过其实它最大的作用是比权值线段树空间少个 \log v。

应该是可以做绝大部分权值线段树支持做的东西的。

提交记录（8.22s）

存在只维护一个中值的实现，具体来讲就是我们发现只需要这个中值是左中值和右中值任意之一，也就是 mid 的前驱或者后继就是对的。

注意，这个是递归建的，所以可能原树存在更接近 mid 的，不过它被分配给父亲了。

所以我们记一下每个点维护的是左中值还是右中值，然后只在插入的点在 mid 的同一侧且更近的时候再交换。

这样就感觉不比一般平衡树难写了。

感觉这个东西比 fhq-treap 好写，有没有感觉。

提交记录（8.53s）

不过不知道为啥跑的更慢，可能是树高卡的更满导致的。

这个东西在值域为 n 时自动就是一颗几乎完全平衡的二叉树。

这个性质可能有些奇怪的用途。

upd：我错了，这个跑得比红黑树快，带快读喜提 6.08s。

先序版

考虑把这个东西改成先序遍历的，如果插入值小于当前值就 swap 一下，如果新的插入值在 [l,mid] 内，就往左儿子插，反之就往右儿子插。

复杂度显然还是对的，于是我们就成功爆了曾经的先序遍历平衡树。

还是比红黑树快，但是不知道为啥跑的更慢了

upd: 卡常成果

如果你将 \log (r - l + 1) 当作 treap 的那个随机值的话，你会发现这个就是一个奇异的 treap，靠 swap 优先级来实现插入。

这个思路非常的优秀，如果我们发现加的点的优先级不满足堆性质，那为啥不改一下优先级呢？

这个东西可能支持调整优先级，如上升优先级就是把最大/最小值拿上来，下降优先级就是反过来，所以可能可以支持 2 个 log 的合并，但似乎比较复杂，鉴定为不如 fhq。