一种可以维护历史版本的线段树，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$。
显然如果对每个历史版本都重建线段树保存时间复杂度和空间复杂度均为 $O\left(nm\right)$。
但如果可以重复利用部分结点信息，则可以降低时间复杂度和空间复杂度。
考虑仅对线段树修改路径上的点进行复制、修改，每次修改的时间复杂度和空间复杂度可降为$O\left(\log n\right)$。
题意
维护一个长度为 $n$ 的数组，支持下列操作：
1. 在某个历史版本上修改某一个位置上的值。
2. 访问某个历史版本上的某一位置的值。
每进行一次操作就会生成一个新的版本，版本编号即为当前操作的编号。
题解
用可持久化线段树维护数组，线段树叶子节点记录对应对应位置数组数值，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$。
题意
维护一个长度为 $n$ 的数组，$m$ 次查询，每次查询给定闭区间内第 $k$ 小的数。
题解
关于第 $k$ 小问题，首先想到使用类似名次树的方法查询。
记数组元素为 $a[1\sim n]$，建立空线段树，依次在线段树第 $a[i]$ 位置插入一个元素，线段树需维护区间所含元素个数，并记录历史版本。
设查询区间为 $[l,r]$ ，这历史版本 $r$ 与 历史版本 $l-1$ 的对应节点差值即为 元素 $a[l\sim r]$ 在节点维护范围内所含元素个数。
在此基础上，便可以使用名次树查询第 $k$ 小元素，同时考虑到数据范围需要对数组进行离散化，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$。
题意
维护 $n$ 个集合，每个集合初始时只有一个元素 $i$。
接下来 $m$ 操作，操作分三种：
1. 合并 $a$ ，$b$ 所在集合。
2. 回到第 $k$ 次操作状态。
3. 询问 $a$ ，$b$ 是否在同一集合。
题解
显然不能用路径压缩，可以考虑启发式合并，将深度小的集合并到深度大的里面。
考虑将普通版本的启发式合并的数组改成可持久化数组即可，时间复杂度 $O\left(n+m\log^2 n\right)$ ，空间复杂度为 $O\left(n+m\log n\right)$。