可持久化并查集标题里的“根”到底是哪个根是并查集森林里每棵树的根还是可持久化线段树的根如果不把这两个“根”分开很多人在学习这个算法时会先被字面意思绕晕。先说结论可持久化并查集并没有想象中那么难。它本质上就是“可持久化数组 按秩合并的并查集”。真正难住大多数人的不是并查集本身而是“版本”和“根”之间的关系。你把一棵可持久化线段树的根节点保存下来就等于保存了整个版本的并查集状态哪怕并查集内部有一片森林外部也只需要一个根节点来索引它。这篇文章会把通常做成动画演示的过程拆解成一张张“关键帧”来讲。目标是让零基础读者也能照着实现一遍并且搞清楚三个问题为什么要可持久化为什么不能用路径压缩为什么一片森林只需要保存一个根1. 并查集的本质维护集合的“森林”1.1 并查集到底在维护什么并查集Disjoint Set Union简称 DSU解决的是“集合合并”和“元素归类”两类问题。比如有 5 个人初始每个人自成一个集合某次操作让 1 号和 2 号成为朋友那么“1 和 2 在同一个集合里”这个事实要被记录下来再让 3 号和 4 号成为朋友又产生一个新集合。并查集使用两个核心操作find(x)找到元素 x 所在集合的代表元素也叫根。merge(x, y)把 x 所在集合和 y 所在集合合并成一个集合。这里的“根”是第一个重要概念。每个集合被组织成一棵树树的根就是集合代表元素。find(x)就是不断沿着父指针向上走直到走到某个节点的父指针指向自己。1.2 森林是怎么形成的先看一个最简单的例子。初始时每个节点都是独立的根节点1 2 3 4 5执行merge(1, 2)让 1 的父指针指向 2并以 2 作为集合代表1 - 2 3 4 5此时有两个根节点2 单独是一棵树的根3、4、5 也各是一棵树的根。多个根节点并存这就是“树组成森林”的来源。如果我们再执行merge(3, 4)树变成1 - 2 3 - 4 5此时森林里依然有多棵互不相交的树。所以“并查集 森林”是一个天然的组合并查集内部并不是一棵树而是多棵树。1.3 路径压缩和按秩合并各自解决了什么原始并查集有两套优化手段。路径压缩在find(x)的过程中把沿途经过的节点直接挂到根节点下面。这样下次再查这些节点时走的路径会非常短。int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); }按秩合并在合并时把“树高更低”或者“子树规模更小”的树接到另一棵树的根上避免树变成一条长链。void merge(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (sz[rx] sz[ry]) swap(rx, ry); fa[rx] ry; sz[ry] sz[rx]; }在普通并查集里这两个优化可以同时使用效果也很好。但一旦进入“可持久化”的语境路径压缩就会变成一个麻烦。这一点在后面第 3 章会重点解释。2. 可持久化从“当前状态”到“版本管理”2.1 为什么要可持久化普通并查集只维护“当前状态”。每一次合并都会把之前的父指针覆盖掉。如果需要回答“第 k 次操作之后x 和 y 是否连通”普通并查集就做不到了因为第 k 次操作时的状态已经被后面的操作覆盖。这类问题并不罕见。文本编辑器的撤销、代码分支管理、数据库的整体快照都有类似需求。算法竞赛中常见的表述是操作基于某个历史版本执行查询某个历史版本中两个元素是否连通“回到第 k 次操作后的状态”。要支持这些操作就需要让数据结构具备“版本”属性每次修改产生一个新版本历史版本不丢失且不把原有数据复制一遍。2.2 可持久化数组的本质可持久化并查集的底层不是“并查集本身”而是一个可持久化数组——通常用可持久化线段树实现。可持久化线段树的思想很朴素每次修改一个位置时不直接改动原来的节点而是从根到叶子复制出一条路径在这条复制出来的路径上做修改其他分支继续复用原版本。举个例子。假设父数组初始是下标: 1 2 3 4 5 取值: 1 2 3 4 5把下标 1 的值改成 2。理论上新数组是这样下标: 1 2 3 4 5 取值: 2 2 3 4 5如果保存两个完整的数组每次修改都是 O(n) 的复制成本完全不可接受。可持久化线段树的方案是复制的不是整个数组而是从根到叶子的一条链。版本 0 [1] [2] [3] [4] [5] 版本 1 [2] [2] [3] [4] [5] ↑ 只对根到下标 1 这条路径新建节点其他节点复用版本 0因此一次单点修改的时空成本是 O(log n)而不是 O(n)。这就是可持久化数组的核心价值。2.3 数据结构的“根”和并查集的“根”不是一回事在第 1 章里并查集中的“根”指一棵树的代表元素。而在可持久化线段树中“根”是整个数据结构版本的入口。这两个概念容易混淆。标题里的“一片森林为什么只保存一个根”问的其实是并查集明明是若干棵树的森林为什么我们只需要记录一个根节点就够了答案是这个根不是并查集森林里某棵树的根而是“可持久化线段树版本”的根。通过它可以查到该版本下任何一个数组位置的值而并查集森林里的多个树根都只是这个数组中的普通值。换句话说概念位置作用并查集的根数组 val[pos] 中的一个取值表示某棵集合树的代表元素可持久化线段树的根lc/rc/val 数组的下标表示某个版本的完整状态入口理解了这个区分标题的疑问就解开了一大半。3. 核心问题为什么一片森林只需保存一个根3.1 把并查集搬到可持久化数组上普通并查集需要两个数组fa[x]记录 x 的父节点sz[x]记录以 x 为根的树的大小用于按秩合并。可持久化版本不直接开两个数组而是开两棵可持续化线段树第一棵线段树维护fa数组第二棵线段树维护sz数组。每个版本记录两个根节点rootFa[ver]和rootSz[ver]。执行find(x)时不是在fa数组里直接取fa[x]而是通过可持久化线段树的单点查询取出“某个版本下的fa[x]”。3.2 为什么不能直接使用路径压缩这是可持久化并查集最容易踩坑的地方。路径压缩的核心动作是在find的过程中把路径上所有节点直接指向根节点。这意味着一句话中可能修改很多个父指针。放在可持久化结构里每个父指针的修改都是一次update每次update又会新增 O(log n) 个节点。路径压缩之后树高会变得很低但代价是一次 find 可能产生 O(m) 次单点修改每次修改在可持久化线段树中新增 O(log n) 个节点实现复杂度大幅上升常数非常大。标准做法是放弃路径压缩只使用按秩合并。按秩合并保证什么它保证并查集树的高度始终是 O(log n)。即使没有路径压缩find的一次向上跳转也最多走 O(log n) 步。每一层跳转再配合线段树的单点查询 O(log n)总复杂度仍可接受。所以可持久化并查集的一个经典复杂度结论是find时间复杂度O(log² n)merge时间复杂度O(log² n)每生成一个新版本新增节点数O(log n)版本回退O(1)。3.3 一次 merge 操作的“动画关键帧”我们用一组“关键帧”描述一次合并。假设当前是整个版本 0 的初始状态执行merge(1, 2)。关键帧一查询两个元素的根。find(1) - 1 find(2) - 2关键帧二按秩合并决定谁指向谁。两端树大小相同按代码约定把 1 的父指针指向 2。关键帧三修改fa[1] 2生成新的 parent 线段树版本。版本0 parent: [1, 2, 3, 4, 5] 版本1 parent: [2, 2, 3, 4, 5] ↑ 只有下标 1 被修改关键帧四修改sz[2] sz[2] sz[1]生成新的 size 线段树版本。版本0 size: [1, 1, 1, 1, 1] 版本1 size: [1, 2, 1, 1, 1] ↑ 只有下标 2 被修改外部只需要记录两个新根rootFa[1]和rootSz[1]。所有未被修改的位置新版本和旧版本共享同一批节点。这就是“可持久化”的直觉每次操作不是推翻重来而是“复制一条路径 改一个叶子 复用其余部分”。4. 环境准备与数据结构设计4.1 开发环境本文代码使用 C17 编写。不涉及第三方库在 Linux、macOS、Windows 的任意编译环境都可以运行。推荐至少支持 C14 的编译器因为代码中使用了using namespace std和 C17 特性较少核心部分在 C11 标准下也能编译通过。在评测机上提交时如果遇到“编译错误”或“未定义引用”优先检查代码块中是否有不符合当前 C 标准的语法。4.2 数据结构字段说明实现中需要几个全局数组lc[u]、rc[u]可持久化线段树节点的左右孩子下标val[u]当前节点的值仅叶子节点有意义tot动态节点分配计数器从 1 开始递增rootFa[ver]第 ver 个版本中fa 数组所对应线段树的根rootSz[ver]第 ver 个版本中size 数组所对应线段树的根。空间估算要特别注意。每次update会沿根到叶子新建一条链链长是 O(log n)。一次合并需要两次 update所以最多新增节点数大约是操作次数乘以 O(log n)。因此数组大小通常开到const int MAXN 1e5 5; const int MAXM 2e5 5; const int MAXNODE MAXN * 25 MAXM * 40;“25”和“40”是经验系数不是精确数学公式。如果题目数据范围更大需要按(n m) * log n适当放大再留 10% 到 20% 余量。5. 可持久化并查集的完整实现5.1 可持久化数组模板以下代码实现了可持久化线段树的基础步骤建立、单点修改、单点查询。// 文件路径persistent_array.cpp #include bits/stdc.h using namespace std; const int MAXNODE 3000000; int lc[MAXNODE], rc[MAXNODE], val[MAXNODE]; int tot 0; // 建树数组下标从 l 到 r初始化成数组 a 中的值 int build(int l, int r, int *a) { int cur tot; if (l r) { val[cur] a[l]; return cur; } int mid (l r) 1; lc[cur] build(l, mid, a); rc[cur] build(mid 1, r, a); return cur; } // 单点修改在 pre 指向的老版本基础上把 pos 位置改成 v返回新节点下标 int update(int pre, int l, int r, int pos, int v) { int cur tot; lc[cur] lc[pre]; rc[cur] rc[pre]; val[cur] val[pre]; if (l r) { val[cur] v; return cur; } int mid (l r) 1; if (pos mid) { lc[cur] update(lc[pre], l, mid, pos, v); } else { rc[cur] update(rc[pre], mid 1, r, pos, v); } return cur; } // 单点查询在根为 rt 的版本中查询 pos 位置的值 int query(int rt, int l, int r, int pos) { if (l r) { return val[rt]; } int mid (l r) 1; if (pos mid) { return query(lc[rt], l, mid, pos); } return query(rc[rt], mid 1, r, pos); }这三个函数是后续所有版本操作的地基。注意update总是先复制pre节点的左右孩子和值再沿目标方向递归。递归返回后当前节点的对应孩子被替换为新子树的根。旧版本pre完全没有被修改。5.2 可持久化并查集的核心操作并查集操作在可持久化版本下不再直接访问fa[x]而是通过query从版本根中取出值。由于不使用路径压缩find只需要递归向上找根。// 文件路径persistent_dsu.cpp // n 表示元素个数rootFa[ver] 与 rootSz[ver] 保存版本根 int n, m; int rootFa[MAXM], rootSz[MAXM]; // 在版本 ver 中查找 x 的根 // 这里不使用路径压缩只做纯向上跳转 int findRoot(int ver, int x) { int f query(rootFa[ver], 1, n, x); if (f x) { return x; } return findRoot(ver, f); } // 查询版本 ver 中根为 x 的集合大小 int getSize(int ver, int x) { return query(rootSz[ver], 1, n, x); } // 在版本 ver 中合并 x 和 y结果写回 rootFa[ver] 和 rootSz[ver] void mergeSet(int ver, int x, int y) { int rx findRoot(ver, x); int ry findRoot(ver, y); if (rx ry) { return; } int sx getSize(ver, rx); int sy getSize(ver, ry); // 按秩合并size 大的当根 if (sx sy) { swap(rx, ry); swap(sx, sy); } // 把 rx 的父节点指向 ry int newParentRoot update(rootFa[ver], 1, n, rx, ry); // 更新 ry 的集合大小 int newSizeRoot update(rootSz[ver], 1, n, ry, sx sy); rootFa[ver] newParentRoot; rootSz[ver] newSizeRoot; } // 判断版本 ver 中 x 和 y 是否连通 bool isConnected(int ver, int x, int y) { return findRoot(ver, x) findRoot(ver, y); }这段代码里最关键的一点是findRoot传递的ver从外部版本号传入在递归过程中始终保持同一个版本。它绝不能在递归过程中修改任何值。5.3 完整主程序示例下面用一个完整程序演示“基于历史版本操作”的流程。输入格式约定如下1 a x y基于版本 a合并 x 和 y生成一个新版本。2 a回到版本 a生成一个新版本新版本状态与 a 相同。0 a x y查询版本 a 中 x 和 y 是否连通输出 0 或 1。// 文件路径main.cpp #include bits/stdc.h using namespace std; const int MAXN 100005; const int MAXM 200005; const int MAXNODE MAXN * 25 MAXM * 40; int lc[MAXNODE], rc[MAXNODE], val[MAXNODE]; int tot 0; int n, m; int rootFa[MAXM], rootSz[MAXM]; int INIT_FA[MAXN], INIT_SZ[MAXN]; // 这里省略 build/update/query 的实现 // 请把 5.1 中的三个函数复制到此处 int findRoot(int ver, int x) { int f query(rootFa[ver], 1, n, x); if (f x) return x; return findRoot(ver, f); } int getSize(int ver, int x) { return query(rootSz[ver], 1, n, x); } void mergeSet(int ver, int x, int y) { int rx findRoot(ver, x); int ry findRoot(ver, y); if (rx ry) return; int sx getSize(ver, rx); int sy getSize(ver, ry); if (sx sy) { swap(rx, ry); swap(sx, sy); } int newParentRoot update(rootFa[ver], 1, n, rx, ry); int newSizeRoot update(rootSz[ver], 1, n, ry, sx sy); rootFa[ver] newParentRoot; rootSz[ver] newSizeRoot; } bool isConnected(int ver, int x, int y) { return findRoot(ver, x) findRoot(ver, y); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) { INIT_FA[i] i; INIT_SZ[i] 1; } // 版本 0 是初始状态 int totalVer 0; rootFa[0] build(1, n, INIT_FA); rootSz[0] build(1, n, INIT_SZ); while (m--) { int opt; cin opt; if (opt 1) { int a, x, y; cin a x y; totalVer; rootFa[totalVer] rootFa[a]; rootSz[totalVer] rootSz[a]; mergeSet(totalVer, x, y); } else if (opt 2) { int a; cin a; totalVer; rootFa[totalVer] rootFa[a]; rootSz[totalVer] rootSz[a]; } else { int a, x, y; cin a x y; int ans isConnected(a, x, y); cout ans \n; } } return 0; }主程序的逻辑很简单每次操作先根据题目要求继承某个历史版本的根然后基于它生成新版本或者直接查询。操作 2 的“回退”实际上只是复制一个根节点下标复杂度 O(1)并没有复制整棵树。6. 运行验证如何用一组样例看懂“版本”6.1 测试输入使用下面的输入进行验证。5 6 1 0 1 2 1 1 3 4 1 2 1 3 0 2 1 4 2 3 0 4 1 5逐条操作解析基于版本 0 合并 1 和 2生成版本 1。基于版本 1 合并 3 和 4生成版本 2。基于版本 2 合并 1 和 3生成版本 3。此时 1、2、3、4 在同一个集合中代表元素是 4。查询版本 2 中 1 和 4 是否连通。版本 2 只有“1-2”和“3-4”两个集合1 和 4 不连通。回到版本 3生成版本 4。查询版本 4 中 1 和 5 是否连通。版本 4 中 1 与 4 相连5 独立因此不连通。6.2 预期输出0 06.3 如何判断程序是否真的“可持久化”一个简单的自检方法是在主程序执行到第 4 步之前手动打印rootFa[2]和rootFa[3]中节点 1 的祖先路径。版本 2 中节点 1 的父节点是 2节点 2 的父节点是 2版本 3 中节点 1 的父节点仍然是 2但节点 2 的父节点已经变成 4。也就是说版本 2 的线段树中2 - 4的变化并没有污染版本 2 的结果。如果程序在查询版本 2 时输出 1说明某个节点被错误修改了最常见的错误是update函数修改了旧版本节点。另一种验证方法把输出结果去掉换行后与手算结果逐位比对。如果第一行输出 1优先检查mergeSet中是否使用了rootFa[a]而不是rootFa[ver]之外的其他版本根。7. 常见问题与排查思路问题现象可能原因排查方式解决方案空间超限MLEMAXNODE 开得太小节点分配越界打印 tot 最大值观察是否接近数组上限按 (n m) * log n 适当扩大留余量结果错误查询历史版本输出不对update 中直接修改了 pre 节点检查 update 是否先完整复制 lc、rc、val确保新节点先复制旧节点再修改孩子指针递归层数过深导致栈溢出没有按秩合并树退化成链打印每个版本的树最大深度开启按秩合并用 sz 保证树高 O(log n)新版本没有正确继承旧版本把 rootFa[totalVer] 写成新 build 的树检查操作 1 和操作 2 是否先复制根下标使用 rootFa[totalVer] rootFa[a] 继承根查询时出现返回值 0 或越界值查询的 pos 不在 [1, n] 内打印 findRoot 递归中的 x 值检查输入格式确保数组下标从 1 开始如果你在评测环境遇到“段错误”最优先检查的是MAXNODE是否足够。可持久化数据结构的空间占用是初学者最容易低估的部分。宁可一开始开大一个量级也不要因为数组越界浪费两小时。8. 复杂度、局限与工程建议8.1 复杂度总结操作时间复杂度空间变化初始建树O(n)O(n)findRootO(log² n)无mergeSetO(log² n)新增 O(log n) 个节点版本回退O(1)无findRoot的 O(log² n) 由两部分组成向上跳转最多 O(log n) 次每次通过线段树查询值需要 O(log n)。整体上可持久化并查集比普通并查集慢一个对数级别但在算法竞赛和大多数“回退版本”场景中依然足够使用。8.2 可持久化并查集的局限普通并查集可以在 O(α(n)) 时间内完成查找可持久化并查集做不到这一点。原因是路径压缩在可持久化中代价太高只能依靠按秩合并维持平衡。另外这里返回的findRoot(ver, x)不会返回“某个版本中的根节点编号”中的全部信息。它只适合判断连通性。如果你需要查询某个集合的具体成员需要额外维护其他数据结构而不是直接用可持久化并查集。还有一个容易误用的点“回到版本”不是“撤销”。操作“回到版本 a”会生成一个新版本这个新版本的内容等于 a但版本总数仍然增加。它不会把当前版本“删除”也不会影响其他旧版本的存在。8.3 工程上的建议在实际工程里直接写裸数组版可持久化并查集比较少但它背后的“可持久化数组”思想非常值得掌握。以下几个工程建议特别实用使用内存池用全局数组而不是vector来保存可持久化线段树节点避免动态扩容带来的指针失效和性能抖动。封装版本号概念不要让业务代码直接操作rootFa、rootSz数组而是封装成PersistentDSU类提供merge(version, x, y)、same(version, x, y)、rollback(version)等方法。空间估算时预留余量可持久化结构的所有节点都保存在一个池子里极难用完后自动回收。商业项目或长时间运行的进程必须考虑节点淘汰策略。递归深度findRoot和query都是递归函数。在某些极端数据下树高可能接近 log n但递归深度不会太高如果还是担心栈溢出可以把递归改成显式栈或迭代版本。这些建议不只是解决“能跑通”的问题更是在帮你养成写可持久化结构的良好习惯能复用的节点不要新建能复制的根指针不要复制整棵树。9. 总结与延伸可持久化并查集看似被“可持久化”四个字吓住了拆开之后其实只有三层第一层是并查集负责解决“元素是否在同一个集合”的问题第二层是可持久化数组负责给数组加“版本”属性第三层是把二者组装起来用两个独立版本根分别维护fa和sz。标题里的“一片森林为什么只保存一个根”最终的答案是我们保存的“根”不是并查集森林里某棵树的根而是可持久化线段树版本根。一个根节点就是一个版本的完整入口里面的叶子节点装着并查集森林每一棵树根的信息。读完这篇文章后建议完成三个练习手动把 6.1 节的样例跑一遍画出每个版本的fa数组变化。把代码中的findRoot改造成显式栈的迭代写法观察时间变化。对比“回退版本”和“批量撤销最近 k 次操作”两种需求思考为什么前者可以直接复制根下标后者需要额外维护历史版本栈。如果这篇文章对你有帮助建议收藏备用。后续可以继续关注可持久化线段树、可持久化栈、可持久化平衡树。它们底层都共享同一套“路径复制 版本根”的思想一旦想明白几个难点会一次性打通。