学习心得 - 数据结构 - 可持久化

· · 算法·理论

什么是可持久化

可持久化是一种数据结构的性质，可以做到存储历史信息。

思想是只新建多余的点，维护全局历史信息。

可持久化线段树

在普通的线段树的基础上，维护一个版本信息，因为一次修改最多改 \log_2n 个点，所以考虑加点，开销不大，可以执行可持久化。最多增加 q\log_2n 个点。由于是动态新增点，所以我们也需要一个类似动态开点的 cnt 数组来维护当前点数。每一次新增的点初始的信息是和原点相同，然后直接使用标记永久化（Link）就可以维护可持久化节点的值。

可持久化 Trie

主要用于 01 Trie 的可持久化，可以同时查询多个字符串，思想一样。这个东西你可以根据可持久化线段树的结构直接改成 Trie，然后就结束了。

可持久化平衡树

咱只会最好用的 FHQ（Link），那它好用也有好用的道理。因为我们家 Treap 的本质就是不停增加新的点，天生就带一个动态开点，直接加 rt 数组上去就没事了。

可持久化文艺平衡树

你既然会了可持久化平衡树，那么把它改成翻转标记就可以了 XD。