我们有这样一个问题：修改点权，询问链上的点权和。这明显是个树链剖分模版。
但如果还有这些操作呢：断开一条边，连上一条边，保证一直是森林。这就是动态树的一种问题。
而 LCT 就是解决这些问题的优秀数据结构。

替罪羊树是一个优雅的暴力，以均摊 O(log(n)) 的时间复杂度和简单的代码闻名。

treap = tree + heap，就比 BST 多了几行代码。

平衡思路超简单，最早发明的自平衡二叉树，也是查询速度最快的平衡树，

luogu 阅读链接。 定义 BST（二叉搜索树）是一种树形结构，有如下性质。 空树是二叉搜索树。 若左子树非空，那么左子树上所有点的权值均小于其根节点的值。 若左子树非空，那么其右子树上所有点的权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 操作 BST 的单次操作最坏为 O(n)O(n)O(n)，nnn 表示 BST 内的节点数，即树的形态是一条链。 节点定义 ...

可持久化后的数据结构并不会修改什么。它把所有版本都存了下来，每次修改都会新建一个副本，然后将修改作用于副本。这样，它就拥有数据回滚、访问历史版本的能力了。

在 OI 中，红黑树可是跑的最快的，其实很好写，就 100 行够了，希望看完后你能掌握它。

Splay 是最灵活的平衡树，除了常数和不能完全可持久化，它几乎没有缺点。

线段树你肯定会吧，WBLT 就是把线段树和平衡树结合起来了。

fhq-treap 又名“无旋 treap”，有着码量小，易理解，可持久化等特点。