这里之所以把这两个放在一起讲，是因为它们实在是相似度很高（至少在竞赛领域），都需要求kth和指定元素的rank（Treap的话可有可无，但通常会需要）。不过如果你没有写过树，强烈建议你自己通过理解来写一遍。
BST 首先，Treap和SBT都属于BST的一种，BST就是二叉搜索树，它满足的特点是：
二叉树 没有两个节点的值相等 任意子树的根节点的值都比左子树所有节点的值要大 任意子树的根节点的值都比右子树所有节点的值要小 任意子树均为二叉搜索树 如果我们实在需要支持多个相同值放在树里面，那么有两种情况，如果那些相同值是确实完全没有区别（例如int），那么只需要在每个节点多加一个字段记录这个值出现的次数就可以了，但如果这些值只有偏序关系，可能不是严格相等，存在其它非比较字段，那么我们就再在每个节点增加一个next域做成一个链表即可。