可持久化数组：路径复制与共享节点实现历史版本查询

可持久化数组解决的是这样一类问题同一个数组经过多次单点修改后还能随时查询任意历史版本中任意下标的值。普通数组保存的是“当前状态”一次赋值就会覆盖旧值改掉就回不去如果每修改一次就把整个数组复制一份内存和时间又完全不能接受。可持久化数组的关键在于共享节点、只复制修改路径把单次修改的代价从 O(n) 降到 O(log n)同时让旧版本根节点继续保留旧值。算法动画里最能体现这一点的是那棵“会分身”的线段树一次修改不是推倒重来而是沿着根到叶子的路径长出一串新节点旧节点原封不动。理解这条主线就能回答标题里的问题——改过的数为什么还能查回去因为旧数据从来没有被删掉只是不再被新版本引用而已。1. 可持久化数组到底在解决什么问题1.1 普通数组做不到的事普通数组的赋值操作非常直接把某个下标对应的内存单元改成新值。下面这段代码看起来没有任何问题。int a[5] {1, 2, 3, 4, 5}; a[1] 99; // a 现在是 {1, 99, 3, 4, 5}问题在于原来的数组在哪里内存中同一个地址已经被覆盖旧值 2 已经不存在了。如果程序只是处理当前状态这当然没问题但一旦业务逻辑需要撤销、重放、回到某次修改之前的版本普通数组就无能为力。这类场景在工程里很常见编辑器撤销栈、版本化配置、进程快照、在线数据表的历史回溯都会遇到“修改之后还要能读取修改前的值”的需求。数据结构领域把这种能力称为可持久化常见说法是 Persistence。所以可持久化数组要解决的并不是“怎么把数组改得更好”而是“怎么让每一次修改都被完整保存下来并且可以在任意时刻查询任意历史版本”。1.2 朴素快照方案为什么不可行最容易想到的方案是做快照每次修改前或修改后把整个数组复制一份存到版本列表里。查询历史版本时直接按下标读取对应版本数组。写成代码大概是这样vectorvectorint versions; versions.push_back(original); // 修改时复制最后一份再修改 vectorint cur versions.back(); cur[pos] value; versions.push_back(cur); // 查询时直接读取 int val versions[ver][pos];这个方案逻辑清晰、查询很快坏在修改成本太高。数组长度为 n每修改一次就要复制 n 个元素修改 m 次总时间 O(n*m)空间也是 O(n*m)。当 n 和 m 都达到 10 万级别时内存会接近灾难。假设每个整数占 4 字节10 万次修改、每次复制 10 万个整数总占用约 40GB任何常规竞赛或业务环境都扛不住。快照方案并不是完全不能用它适合数据量小、修改次数少、查询压力大的场景。但在大数组高频修改的场景里必须换一种更聪明的结构。1.3 可持久化思想的核心不覆盖旧数据共享旧结构可持久化数据结构的设计思路可以概括成两句话旧节点永远不修改。新版本复制需要变化的路径其余部分直接共享旧节点。可持久化数组的典型实现是把数组看成线段树叶子节点上保存的值。线段树的每个节点代表一个区间根节点代表整个数组。初始版本由一棵完整线段树构成执行单点修改时从根节点出发到目标叶子的整条路径上每个节点都新建一份副本路径之外的所有子树继续指向旧版本节点。从外部看修改一次只是多了一条“新根到新叶子”的路径数组的其余部分仍然和旧版本共用。因为旧根没有被改动旧版本依旧可以完整查询因为新根指向的是复制出来的路径新版本也不会干扰旧版本。这样就把单次修改的时间从 O(n) 压缩到了 O(log n)。为了实现这一点需要一棵动态开点的线段树而不是用数组下标 2*i、2*i1 的静态完全二叉树。每个节点必须显式记录左右孩子下标否则无法在多个版本之间共享子树。2. 路径复制原理一次修改为什么要新建 log n 个节点2.1 线段树是天然的版本容器可持久化数组为什么选择线段树而不是直接改造普通数组原因在于线段树天然具备“用区间索引定位单点”的能力。一颗长度为 n 的线段树深度约 log2(n)1。从根走到任意一个叶子需要经过的节点数也就是这个深度。可持久化单点修改时只有这条路径上的节点值或孩子指针会发生变化因此只需要复制这些节点。路径外的兄弟子树保持不变可以被新版本直接共享。以数组 [1,2,3,4,5] 为例初始版本 root0 的线段树一共 9 个节点5 个叶子4 个内部节点。如果修改下标 2 为 99从根节点到叶子 [2,2] 的路径一共 4 个节点根 [1,5]、内部节点 [1,3]、内部节点 [1,2]、叶子 [2,2]。新版本只需要新建这 4 个节点。这种结构可以抽象成下面的样子root0 root1 [1,5] [1,5] / \ / \ [1,3] [4,5] [1,3]new [4,5]继承 / \ / \ [1,2] [3,3] [1,2]继承 [3,3]继承 / \ [1,1] [2,2]newroot0 仍然指向左侧原来的 [1,5]所以版本 0 的数组还是 [1,2,3,4,5]。root1 指向新的 [1,5]这个新根向左走到新 [1,3]继续向左走到从版本 0 继承下来的 [1,2]再向左走到 [1,1]向右走到新叶子 [2,2]新根的右孩子直接继承版本 0 的 [4,5]。因此版本 1 读到的数组是 [1,99,3,4,5]同时没有破坏版本 0。2.2 一次单点修改的节点变化过程把一次修改拆成更细的步骤可以写成一个标准流程给新根节点分配一个新编号。把旧根节点的 left、right、value 全部复制到新根节点。判断目标下标 pos 属于左子树还是右子树。如果是左子树递归修改左子树并把返回的新左孩子下标赋给新根节点的 left。如果是右子树递归修改右子树并把返回的新右孩子下标赋给新根节点的 right。到达叶子时把新节点的 value 改成目标值。整个过程只复制从根到目标叶子路径上的节点未经过的子树直接保留旧下标。下面用表格说明一次修改会新建哪些节点新节点代表区间创建原因孩子指向根节点[1,5]新版本必须有新根左孩子指向新的 [1,3]右孩子继承旧 [4,5]内部节点[1,3]路径经过左孩子继承旧 [1,2]右孩子继承旧 [3,3]内部节点[1,2]路径经过左孩子继承旧 [1,1]右孩子指向新叶子 [2,2]叶子节点[2,2]目标位置value99这里的关键点是新根虽然代表版本 1但它的很多子孙节点仍然是版本 0 的节点。这就是“共享”的实际含义。2.3 版本根与查询路径保存历史版本并不需要复制整棵树只需要保存一个数组 root下标是版本号值是每个版本根节点在节点池中的下标。root[0] 建树返回的根下标; root[1] 第一次修改返回的新根下标; root[2] 第二次修改返回的新根下标;查询版本 ver 中位置 pos 的值时从 root[ver] 出发按 pos 所在的区间不断向下走直到叶子。为什么这样查询不会读到后续版本的修改因为版本 ver 的根节点保存的是“当时”的树关系。即使后面新建了版本 2、版本 3版本 1 的根节点下标没有变它指向的左孩子、右孩子也没有变。后续版本的修改只会在新路径上创建新节点不可能回头去修改版本 1 路径上已经存在的节点。可以从另一个角度理解可持久化数组不是“数组在变”而是“一棵不断生长的树在记录所有状态”。每次修改只是在树上新增一条路径旧路径永远保持原样。3. C 实现一个最小可运行的可持久化数组3.1 节点设计与内存预分配因为每个节点都要被多个版本共享节点不能在递归函数里以局部变量形式存在必须使用一个全局的节点池。节点结构包含三个字段左孩子下标、右孩子下标、当前节点保存的值。struct Node { int left; int right; int value; };这里 value 只在叶子节点上有实际作用。内部节点的 value 在单点查询实现里不会被用到。如果后续要支持区间和、区间最大值就需要把 value 替换成 sum、max 等聚合字段。节点池大小需要提前估算。初始建树会创建约 2*n 个节点每次修改会创建约 log2(n)1 个节点。如果修改次数为 m总节点数大约是2 * n m * (ceil(log2(n)) 1)为了更稳妥可以在公式后面加一个常数余量。下面代码里按 n 和 m 都取 100000log 约 17 来估算const int MAXN 100005; const int LOGN 18; const int MAXQ 100005; const int MAXNODE MAXN * 2 MAXQ * (LOGN 2); struct Node { int left; int right; int value; }; Node tree[MAXNODE]; int root[MAXQ]; int nodeCnt 0;数组开得比理论值大一些能避免极端数据下段错误。实际生产环境还要根据自己的数据规模重新计算不能照搬。3.2 建树、修改、查询三块核心代码建树负责从数组 a 构造出版本 0。叶子节点记录 a[l]内部节点不需要计算聚合值只需要把左右孩子连起来。int a[MAXN]; int build(int l, int r) { int id nodeCnt; if (l r) { tree[id].value a[l]; return id; } int mid (l r) 1; tree[id].left build(l, mid); tree[id].right build(mid 1, r); return id; }这里要注意 build 访问的 a 是全局数组下标从 1 开始。如果题目要求下标从 0 开始需要统一调整 l、r 和数组下标不要在函数内部混用两套体系。修改操作是路径复制的核心int update(int prev, int l, int r, int pos, int val) { int id nodeCnt; tree[id].left tree[prev].left; tree[id].right tree[prev].right; tree[id].value tree[prev].value; if (l r) { tree[id].value val; return id; } int mid (l r) 1; if (pos mid) { tree[id].left update(tree[prev].left, l, mid, pos, val); } else { tree[id].right update(tree[prev].right, mid 1, r, pos, val); } return id; }update 第一件事是复制旧节点字段而不是直接修改旧节点。复制完成后再修改需要变化的一侧孩子指针另一侧保持继承关系。这样返回的新节点 id 可以安全作为新版本的根。查询操作只读取不创建任何节点int query(int u, int l, int r, int pos) { if (l r) { return tree[u].value; } int mid (l r) 1; if (pos mid) { return query(tree[u].left, l, mid, pos); } return query(tree[u].right, mid 1, r, pos); }整个递归过程始终沿着 pos 所在区间前进最终在叶子返回 value。3.3 完整示例与输入输出验证把上面三块代码组装成完整程序。操作规则如下1 pos val在当前最新版本基础上把 pos 位置改成 val生成一个新版本。2 ver pos查询第 ver 个版本中 pos 位置的值。#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOGN 18; const int MAXQ 100005; const int MAXNODE