分类：信息学竞赛

\(\text{Treap}\)是一种通过维护堆和二叉搜索树两重性质来限制树高的平衡树。

每一个节点都被赋予了两个值，称作\(val\)和\(key\)，分别按照BST和堆的性质维护：

• 小根堆：每一个节点的\(key\)都小于等于他的两个子节点的\(key\)
• 二叉树：每一个节点的\(key\)都比他左子的\(val\)大，比右子的\(val\)小

每一个节点的\(key\)是随机指定的，这样可以保证期望树高为\(\log n\)

继续阅读“Treap”

转自范爷的blog：http://fanhq666.blog.163.com/blog/static/8194342620123352232937/
原始文件：https://blog.edgaru089.ml/custom-items/后缀自动机与线性构造后缀树.txt

冬令营上我犯了最大的一个错误，就是在陈立杰讲后缀自动机的时候睡觉。
这导致了，我在冬令营之后只能花费好几个不眠之夜来思考后缀自动机到底是什么。
突然，在某天的梦里，我看到了一幅神奇的图景，我突然发现，一切都是那么的明晰了。

继续阅读“后缀自动机与线性构造后缀树——转自fanhq666（fhq范爷）”

前置技能：Splay（伸展树）

Link/Cut Tree 是一种维护森林连通性和其他树上问题的思想暴力的数据结构。

它可以干什么呢：
继续阅读“Link/Cut Tree”