可持久化线段树 1（可持久化数组）题解

思路

每个版本只依赖一个更早的版本。把版本看成结点，并从它所依赖的版本向它连边，所有版本便形成一棵以版本 $0$ 为根的树。

沿版本树从父结点进入一个修改结点时，只会改变数组的一个位置；离开该结点时恢复这个位置的旧值。这样，在深度优先遍历到任意版本时，当前数组恰好就是该版本的内容。查询结点直接读取指定位置即可。

为了避免版本树退化成长度为 $m$ 的链时发生递归栈溢出，可以用显式栈完成遍历。查询结果先按操作编号保存，遍历结束后再按原操作顺序输出。

做法

子任务算法

对于 $n,m\le 10^3$，可以为每个新版本完整复制整个数组，再完成修改或查询，时间复杂度为 $O(nm)$。

对于 $n,m\le 10^4$，可以把数组分块。每个版本只复制块指针，修改时再复制包含目标位置的块，得到持久化分块做法。

对于 $n,m\le 10^5$，可以使用可持久化线段树。每次修改只新建从根到目标叶子的 $O(\log n)$ 个结点，查询沿对应版本的根向下查找。

满分算法使用版本树与回滚。每次进入或退出修改版本都只进行常数次赋值，查询也只需常数时间。

正确性证明

考虑版本树深度优先遍历中的任意时刻。对根版本，当前数组就是初始数组，命题成立。

假设进入某个版本前，当前数组等于其父版本。若该版本是修改操作，算法只把指定位置改为给定的新值，所得数组正是该版本；若该版本是查询操作，算法不修改数组，所得数组仍与它复制的父版本相同。因此进入每个版本后，当前数组都等于该版本。

处理完一个修改版本的整棵子树后，算法恢复进入时保存的旧值，故回到父版本时数组状态也被完整恢复；查询版本没有修改，不需要恢复。由归纳可知，每次查询读到的都是指定历史版本中目标位置的真实值。最后按操作编号输出，顺序与题目要求一致。

复杂度分析

建立版本树、遍历版本树和处理所有操作的总时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。