前置请先学会 BST，如果没有弄会 BST 的话建议去这里。 Intro书接上回，我们在 BST 的结尾留下了一个问题：如何将 BST 弄平衡？ 答案是：弄成一颗平衡二叉搜索树！以后我们就将其简称为平衡树。 平衡树有很多类型，今天我们介绍一种入门级的平衡树——Treap。 写一天博文都快累死了。 TheoryTreap 是 Tree + Heap 的合成词。 我们都知道，满足 BST 性质且中序

前言中午写的博文，脑子不大清醒，代码直接重写的没有从写好的粘贴，如果哪里写挂了就按照代码逻辑看下去吧（反正评论区现在不大正常），实在弄不懂了可以去洛谷私信。 Intro我们之前弄了 Treap 的平衡树，顺手我们把 Splay 的也弄了吧。 Treap 通过随机值和堆性质使得 BST 保持平衡，而 Splay 的操作则是不断将某个节点旋转到根节点，使得整棵树仍然满足 BST 的性质并且保持平衡。

IntroBST 是二叉搜索树的简称，我们定义 BST 上每一个节点都有一个关键值，（就是点权好吧）。 BST 上每一个节点都满足以下性质： 该节点所有左子树的关键值都小于等于该节点的关键值。 该节点所有右子树的关键值都大于等于该节点的关键值。 实现建立出于避免越界，减少特殊判断的目的，我们一般会往 BST 里边丢一个负无穷的关键值和一个正无穷的关键值，仅有这两个节点组成的 BST 就是一颗空