可持久化数据结构是什么

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

简介

分类：

• 部分可持久化：每个历史版本都可以访问，但只有最新的版本才可以修改。
• 完全可持久化：每个历史版本都可以访问和修改。
• 融合可持久化：每个历史版本都可以访问和修改，且支持通过合并两个历史版本来创建新版本。

核心思想

一种暴力的想法是将所有数据 $O(n^2)$ 的存下来。
其实这样没有必要，因为每次修改只修改了一部分，另外的部分是没有修改过的。
其他的部分也都存下来就没有必要了。
我们并不用暴力地全部保存，而是在每次操作结束后，仅新建数据结构中发生改变的部分。
这样一来，维护数据结构的时间复杂度没有增加，空间复杂度仅增长为与时间同级的规模。

什么数据结构能可持久化

我们一般认为均摊复杂的数据结构不能可持久化。
比如一棵为链 Splay 反复访问链尾，为了可持久化，那么单次是 $O(n)$ 的，那么总时间就是 $O(nm)$ 的。

懒标记的处理

1. 标记下传
   每次新建左右儿子，然后下传。
   明显常数、空间较大。
2. 标记永久化
   不需要 pushdown，只要在查询的时候统计上就好了。
   常数较小，局限性较大。

可持久化线段树

我们会实现一棵类似这样的线段树：

图丑误喷。
我们在修改时候，复制一下节点，然后只需要维护每个节点的儿子节点就好了。
洛谷P3919可持久化平衡树1。