现阶段常用的可持久化数据结构大概有以下三类：可持久化线段树、并查集、Trie 树。
因此本文将围绕这三个大类来讲。
1.可持久化线段树/可持久化数组
可持久化线段树本来有一个更为脍炙人口的名字，但由于某些原因我们将其称为可持久化线段树。
考虑在单点修改线段树时，由于线段树高 \(\log n\) 层，每层只修改一个节点，因此新建这 \(\log n\) 个节点以保存更改后和更改前的值做到可持久化。
如果是区间修改，我们尝试着使用标记永久化，仅在查询时计算标记的贡献，统计出从根节点到当前区间的节点的标记和，再加上这个区间的值即为所求。
区间赋值可以维护时间戳，查询时找时间戳最大的修改的权值。
接下来是可持久化的经典应用：静态区间第 \(k\) 小。
首先将权值离散化，按照下标顺序以此将每个值加入线段树，这个线段树维护的是每个值的出现次数，运用可持久化线段树维护每加入一个值后线段树的状态。因此，\(l \sim r\) 中每个数出现的次数可以用 \(1\sim r\) 的线段树减去 \(1\sim l - 1\) 的线段树求出，即我们为 \(a_{l\sim r}\) 建了一棵线段树。
接下来考虑如何找到第 \(k\) 小的值，如果当前区间左儿子的值不足 \(k\)，则向右儿子转移，否则向左儿子转移。每个区间左儿子的值 \(v = val_{\operatorname{ls}_y - \operatorname{ls}_x}\)，\(x,y\) 分别是区间左端点减 \(1\) 和右端点线段树当前节点的编号。这一点可以从线段树的加减法推导得出。
单纯推导比较简单，建议多做例题分析。
2.可持久化并查集
基于可持久化数组。
考虑朴素的并查集 merge，我们只将一个点的 fa 改变了，因此可以用可持久化数组维护各个版本的并查集，此时无法使用路径压缩。因此，可以维护 siz 数组，每次将 siz 较小的向较大的合并。
并查集的应用范围大多用来查询连通性，可以猜测到可持久化并查集可以用来维护带有上下界的连通性问题。例如，按边权顺序加入并查集时，可以查询 \(u\) 和 \(v\) 之间是否可以通过一条边权不大于 \(w\) 的路径到达。
3.可持久化 Trie
同样依赖于可持久化线段树的思想，插入一个数或字符串时新建节点，在上一个版本的基础上新建节点。
大部分可持久化数据结构所涉及到的思路是每次操作对整个数据结构的影响不会太大，因此利用重复信息新建一个数据结构。这类压缩重复信息的思想在很多题目中都有应用。