我们有这样一个问题:修改点权,询问链上的点权和。这明显是个树链剖分模版。 但如果还有这些操作呢:断开一条边,连上一条边,保证一直是森林。这就是动态树的一种问题。 而 LCT 就是解决这些问题的优秀数据结构。
替罪羊树是一个优雅的暴力,以均摊 O(log(n)) 的时间复杂度和简单的代码闻名。
treap = tree + heap,就比 BST 多了几行代码。
平衡思路超简单,最早发明的自平衡二叉树,也是查询速度最快的平衡树,
可持久化后的数据结构并不会修改什么。它把所有版本都存了下来,每次修改都会新建一个副本,然后将修改作用于副本。这样,它就拥有数据回滚、访问历史版本的能力了。
在 OI 中,红黑树可是跑的最快的,其实很好写,就 100 行够了,希望看完后你能掌握它。
Splay 是最灵活的平衡树,除了常数和不能完全可持久化,它几乎没有缺点。
线段树你肯定会吧,WBLT 就是把线段树和平衡树结合起来了。
fhq-treap 又名“无旋 treap”,有着码量小,易理解,可持久化等特点。