02.11.4 可持久化与并查集进阶
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.11 高级数据结构
覆盖范围
- 可持久化线段树(主席树)
- 带权并查集
- 可撤销并查集
- 并查集路径压缩与按秩合并
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.11.4-001 | 并查集路径压缩与按秩合并 | 基础 | ★★★★★ |
| 02.11.4-002 | 带权并查集 | 进阶 | ★★★★ |
| 02.11.4-003 | 可撤销并查集 | 高级 | ★★★ |
| 02.11.4-004 | 可持久化线段树(主席树) | 高级 | ★★★ |
| 02.11.4-005 | 主席树求区间第 K 大 | 高级 | ★★★ |
| 02.11.4-006 | 可持久化 vs 可撤销 | 基础 | ★★★ |
| 02.11.4-007 | 离线并查集 | 进阶 | ★★★ |
| 02.11.4-008 | 可持久化数组 | 进阶 | ★★ |
02.11.4-001 并查集路径压缩与按秩合并
频率 ★★★★★ | 难度 基础
一句话结论
并查集用数组 parent[] 表示父节点;find 时路径压缩(把路径上所有节点直接指向根);union 时按秩合并(小树挂大树);两者结合均摊 O(α(n)),α 为反阿克曼函数。
概念解释
- parent[i]:i 的父节点。
- find:找根,路径压缩。
- union:合并两个集合,按秩合并。
- 均摊复杂度:O(α(n)),近似常数。
原理流程
- find(x):if parent[x] != x,parent[x] = find(parent[x]),return parent[x]。
- union(x, y):rx = find(x),ry = find(y);按秩把小树根挂到大树根。
代码 / 示例
class UnionFind {
private final int[] parent;
private final int[] rank;
UnionFind(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
parent[ry] = rx;
if (rank[rx] == rank[ry]) rank[rx]++;
}
}
常见误区
- 误区:路径压缩后还要按秩合并;正解:路径压缩后树高很小,按秩合并作用有限,但保留无妨。
- 误区:find 用迭代;正解:递归更简洁,深度大时改迭代。
追问 / 延伸
- Q:α(n) 是什么? A:反阿克曼函数,增长极慢,n < 1e80 时 α(n) <= 4。
- Q:只路径压缩不按秩合并? A:均摊 O(log n),也够用。
02.11.4-002 带权并查集
频率 ★★★★ | 难度 进阶
一句话结论
在普通并查集基础上维护 weight[x] 表示 x 到根的距离;find 时路径压缩同步更新 weight;union 时根据已知关系计算两个根之间的距离。
概念解释
- weight[x]:x 到父节点的距离。
- find:路径压缩时,weight[x] = weight[x] + weight[parent[x]]。
- union:已知 x 到 y 的关系,计算根之间的距离。
原理流程
- find(x):if parent[x] != x,root = find(parent[x]);weight[x] += weight[parent[x]];parent[x] = root。
- union(x, y, relation):已知 x 到 y 的关系,计算 rootX 到 rootY 的距离,更新 weight[rootX]。
代码 / 示例
class WeightedUF {
private final int[] parent;
private final int[] weight; // weight[x] = x 到 parent[x] 的距离
WeightedUF(int n) {
parent = new int[n]; weight = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) {
int p = parent[x];
parent[x] = find(p);
weight[x] += weight[p];
}
return parent[x];
}
// 已知 x 到 y 的距离为 d(x - y = d),合并
void union(int x, int y, int d) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
parent[rx] = ry;
weight[rx] = weight[y] - weight[x] + d;
}
// 查询 x 到 y 的距离
int distance(int x, int y) {
if (find(x) != find(y)) return -1;
return weight[x] - weight[y];
}
}
常见误区
- 误区:路径压缩时不更新 weight;正解:必须同步更新 weight,否则距离错误。
- 误区:union 时 weight 公式写错;正解:weight[rx] = weight[y] - weight[x] + d(根据已知关系推导)。
追问 / 延伸
- Q:带权并查集用于什么? A:食物链问题、亲戚关系、差分约束。
- Q:权值可以是关系吗? A:可以,如 x 是 y 的父亲/儿子/同类。
02.11.4-003 可撤销并查集
频率 ★★★ | 难度 高级
一句话结论
不用路径压缩(路径压缩不可逆),只用按秩合并;用栈记录每次 union 的修改;撤销时弹栈恢复;支持回滚操作,适合离线分治。
概念解释
- 不用路径压缩:因为路径压缩改了 parent,不可逆。
- 按秩合并:只改一次 parent 和 rank,可记录。
- 栈:记录每次 union 修改了哪些字段。
原理流程
- union(x, y):rx = find(x),ry = find(y);按秩把 ry 挂到 rx;记录 (ry, rx, oldRankRx) 入栈。
- undo():弹栈,恢复 parent[ry] = ry,rank[rx] = oldRankRx。
- find 不路径压缩,O(log n)。
代码 / 示例
class RollbackUF {
private final int[] parent, rank;
private final java.util.Deque<int[]> stack = new java.util.ArrayDeque<>();
RollbackUF(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) { stack.push(null); return; }
if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
stack.push(new int[]{ry, rx, rank[rx]});
parent[ry] = rx;
if (rank[rx] == rank[ry]) rank[rx]++;
}
void undo() {
int[] last = stack.pop();
if (last == null) return;
parent[last[0]] = last[0];
rank[last[1]] = last[2];
}
}
常见误区
- 误区:可撤销并查集用路径压缩;正解:路径压缩不可逆,不能用。
- 误区:撤销时不恢复 rank;正解:rank 也要恢复。
追问 / 延伸
- Q:可撤销并查集用于什么? A:离线分治、线段树分治、动态图连通性。
- Q:find 复杂度? A:不用路径压缩,O(log n)。
02.11.4-004 可持久化线段树(主席树)
频率 ★★★ | 难度 高级
一句话结论
可持久化线段树保存每次修改后的历史版本;新版本只创建修改路径上的 O(log n) 个新节点,其他节点复用旧版本;空间 O(q log n),q 为操作数。
概念解释
- 历史版本:每次修改生成新版本。
- 共享节点:未修改的子树复用旧版本节点。
- 新节点:修改路径上的 O(log n) 个节点新建。
原理流程
- 初始版本:建树。
- 修改:从根开始,新建节点,子树复用旧版本。
- 查询:在指定版本上查询。
代码 / 示例
class PersistentSegTree {
static class Node {
int left, right, sum;
}
private final Node[] tree;
private int[] roots;
private int cnt = 0;
private final int n;
PersistentSegTree(int n, int q) {
this.n = n;
tree = new Node[q * 40];
roots = new int[q];
for (int i = 0; i < tree.length; i++) tree[i] = new Node();
}
int build(int l, int r) {
int node = ++cnt;
if (l == r) return node;
int mid = (l + r) / 2;
tree[node].left = build(l, mid);
tree[node].right = build(mid + 1, r);
return node;
}
int update(int prev, int l, int r, int pos, int val) {
int node = ++cnt;
tree[node].sum = tree[prev].sum + val;
if (l == r) return node;
int mid = (l + r) / 2;
if (pos <= mid) {
tree[node].left = update(tree[prev].left, l, mid, pos, val);
tree[node].right = tree[prev].right;
} else {
tree[node].left = tree[prev].left;
tree[node].right = update(tree[prev].right, mid + 1, r, pos, val);
}
return node;
}
}
常见误区
- 误区:每次修改都新建整棵树;正解:只新建修改路径上的 O(log n) 个节点。
- 误区:新版本和旧版本共享节点;正解:共享未修改的子树,修改路径上新建。
追问 / 延伸
- Q:主席树用于什么? A:区间第 K 大、静态区间第 K 小。
- Q:空间复杂度? A:O(q log n),q 为操作数。
02.11.4-005 主席树求区间第 K 大
频率 ★★★ | 难度 高级
一句话结论
对数组离散化后建主席树,root[i] 表示前 i 个数插入后的版本;查询区间 [l, r] 第 K 大:在 root[r] 和 root[l-1] 上同步二分,左子树数量差 >= K 则往左,否则往右。
概念解释
- 离散化:数值范围大,先排序去重。
- root[i]:前 i 个数的版本。
- 查询:两个版本同步走,左子树数量差判断。
原理流程
- 离散化数组值。
- 依次插入每个数,建 root[i]。
- 查询 [l, r] 第 K 大:在 root[r] 和 root[l-1] 上同步走,左子树数量差 >= K 往左,否则往右。
代码 / 图示
root[i] = 前 i 个数插入后的主席树
查询 [l, r] 第 K 大:
在 root[r] 和 root[l-1] 上同步走
左子树数量差 = countLeft(root[r]) - countLeft(root[l-1])
若 >= K:往左走,K 不变
否则:往右走,K -= 左子树数量差
常见误区
- 误区:不离散化;正解:数值范围大,必须离散化。
- 误区:查询时只在 root[r] 上走;正解:必须两个版本同步走,数量差才是区间内数量。
追问 / 延伸
- Q:时间复杂度? A:建 O(n log n),查询 O(log n)。
- Q:空间复杂度? A:O(n log n)。
02.11.4-006 可持久化 vs 可撤销
频率 ★★★ | 难度 基础
一句话结论
可持久化保存所有历史版本,可查询任意版本;可撤销只回滚到上一版本,不保留历史;可持久化空间 O(q log n),可撤销用栈 O(q)。
概念解释
- 可持久化:保存所有历史版本,可查询任意版本。
- 可撤销:只回滚到上一版本,不保留历史。
- 空间:可持久化 O(q log n),可撤销 O(q)。
原理流程
- 需要查询任意历史版本:可持久化。
- 只需要回滚到上一步:可撤销。
- 可持久化用共享节点,可撤销用栈记录修改。
代码 / 图示
特性 可持久化 可撤销
历史版本 全部保留 只回滚
空间 O(q log n) O(q)
查询 任意版本 只当前
实现 共享节点 栈记录
常见误区
- 误区:可持久化就是可撤销;正解:可持久化保留所有历史,可撤销只回滚。
- 误区:可持久化空间小;正解:可持久化 O(q log n),比可撤销 O(q) 大。
追问 / 延伸
- Q:可持久化并查集? A:可以,但实现复杂,用可持久化数组实现 parent。
- Q:可撤销并查集用于什么? A:离线分治,不需要查询历史版本。
02.11.4-007 离线并查集
频率 ★★★ | 难度 进阶
一句话结论
离线处理所有查询和操作,按时间顺序或特定顺序排序后用并查集;常见于动态连通性问题,把删除操作转化为逆序插入。
概念解释
- 离线:先读所有操作和查询,再排序处理。
- 删除转插入:逆序处理,删除变成插入。
- 并查集:维护连通性。
原理流程
- 读所有操作和查询。
- 标记哪些边存在。
- 逆序处理:删除操作变成插入(加边)。
- 查询时用并查集判断连通性。
代码 / 图示
动态连通性问题:
操作:加边、删边、查询连通
离线:
逆序处理:删边 -> 加边
查询:并查集判断连通
常见误区
- 误区:离线并查集用路径压缩;正解:逆序插入不需要回滚,可以用路径压缩。
- 误区:删除操作直接删;正解:逆序后删除变成插入。
追问 / 延伸
- Q:离线并查集 vs 可撤销并查集? A:离线并查集逆序处理,可撤销并查集在线回滚。
- Q:动态连通性在线怎么做? A:用 Link-Cut Tree 或动态图连通性,复杂。
02.11.4-008 可持久化数组
频率 ★★ | 难度 进阶
一句话结论
可持久化数组用可持久化线段树实现,每次修改生成新版本;支持查询任意历史版本的值;空间 O(q log n)。
概念解释
- 可持久化线段树:保存历史版本。
- 数组:线段树叶子节点即数组元素。
- 查询:在指定版本上查叶子节点。
原理流程
- 初始版本:建树。
- 修改:更新叶子节点,生成新版本。
- 查询:在指定版本上查叶子节点。
代码 / 图示
可持久化数组 = 可持久化线段树
叶子节点 = 数组元素
修改叶子 = 生成新版本
查询版本 = 在指定版本上查叶子
常见误区
- 误区:可持久化数组用数组直接复制;正解:直接复制 O(n),用可持久化线段树 O(log n)。
- 误区:可持久化数组空间 O(n);正解:O(q log n)。
追问 / 延伸
- Q:可持久化数组用于什么? A:历史版本查询,如编辑器撤销。
- Q:可持久化数组 vs 可撤销数组? A:可持久化保留所有历史,可撤销只回滚。
待整理清单
- [ ] 可持久化 Trie
- [ ] 线段树分治
- [ ] 动态图连通性