莞中 2022暑假训练题02:平衡树()

FHQ-Treap

此文章所有代码中的平衡树均为 FHQ-Treap。

FHQ-treap 即非旋Treap,是一种短小精悍,功能丰富的平衡树。

据说它的效率介于 Treap 和 Splay 之间(可能是我的FHQ常数比较小,跑得比我的Treap还快)。

它可以实现 Splay 可以实现的所有功能,包括平衡树的基本操作和区间翻转操作。

它的实现难度比 Splay 要简单很多,没有 Splay 那么多转来转去的操作,不会令人头晕,而且FHQ代码的对称性良好,易于调试。

有两种 FHQ-Treap,一种是按值为关键字的,一种是按下标为关键字的(适用于区间翻转等操作时)。

FHQ-Treap 的核心操作为 \(\text{split}\) (分裂) 和 \(\text{merge}\) (合并)。

\(\text{split}(root,val,x,y)\) 表示将 \(root\) 的子树拆分为两半,一半中的值(或下标)都小于等于 \(val\), 一半的值都大于 \(val\)。

\(\text{merge}(x,y)\) 表示将 \(x\) 子树和 \(y\) 子树合并起来。

具体操作都是依靠 \(\text{split}\) 和 \(\text{merge}\) 来实现的。

按值为关键字时的写法参考 这个博客。

按下标为关键字时的写法可以参考 这个博客。

T1

————————

FHQ-Treap

此文章所有代码中的平衡树均为 FHQ-Treap。

FHQ-treap 即非旋Treap,是一种短小精悍,功能丰富的平衡树。

据说它的效率介于 Treap 和 Splay 之间(可能是我的FHQ常数比较小,跑得比我的Treap还快)。

它可以实现 Splay 可以实现的所有功能,包括平衡树的基本操作和区间翻转操作。

它的实现难度比 Splay 要简单很多,没有 Splay 那么多转来转去的操作,不会令人头晕,而且FHQ代码的对称性良好,易于调试。

有两种 FHQ-Treap,一种是按值为关键字的,一种是按下标为关键字的(适用于区间翻转等操作时)。

FHQ-Treap 的核心操作为 \(\text{split}\) (分裂) 和 \(\text{merge}\) (合并)。

\(\text{split}(root,val,x,y)\) 表示将 \(root\) 的子树拆分为两半,一半中的值(或下标)都小于等于 \(val\), 一半的值都大于 \(val\)。

\(\text{merge}(x,y)\) 表示将 \(x\) 子树和 \(y\) 子树合并起来。

具体操作都是依靠 \(\text{split}\) 和 \(\text{merge}\) 来实现的。

按值为关键字时的写法参考 这个博客。

按下标为关键字时的写法可以参考 这个博客。

T1