罗罗编程学习记录
本页内容 展开查看

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)),近似常数。

原理流程

  1. find(x):if parent[x] != x,parent[x] = find(parent[x]),return parent[x]。
  2. 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 的关系,计算根之间的距离。

原理流程

  1. find(x):if parent[x] != x,root = find(parent[x]);weight[x] += weight[parent[x]];parent[x] = root。
  2. 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 修改了哪些字段。

原理流程

  1. union(x, y):rx = find(x),ry = find(y);按秩把 ry 挂到 rx;记录 (ry, rx, oldRankRx) 入栈。
  2. undo():弹栈,恢复 parent[ry] = ry,rank[rx] = oldRankRx。
  3. 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) 个节点新建。

原理流程

  1. 初始版本:建树。
  2. 修改:从根开始,新建节点,子树复用旧版本。
  3. 查询:在指定版本上查询。

代码 / 示例

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 个数的版本。
  • 查询:两个版本同步走,左子树数量差判断。

原理流程

  1. 离散化数组值。
  2. 依次插入每个数,建 root[i]。
  3. 查询 [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)。

原理流程

  1. 需要查询任意历史版本:可持久化。
  2. 只需要回滚到上一步:可撤销。
  3. 可持久化用共享节点,可撤销用栈记录修改。

代码 / 图示

特性       可持久化          可撤销
历史版本   全部保留          只回滚
空间       O(q log n)       O(q)
查询       任意版本          只当前
实现       共享节点          栈记录

常见误区

  • 误区:可持久化就是可撤销;正解:可持久化保留所有历史,可撤销只回滚。
  • 误区:可持久化空间小;正解:可持久化 O(q log n),比可撤销 O(q) 大。

追问 / 延伸

  • Q:可持久化并查集? A:可以,但实现复杂,用可持久化数组实现 parent。
  • Q:可撤销并查集用于什么? A:离线分治,不需要查询历史版本。

02.11.4-007 离线并查集

频率 ★★★ | 难度 进阶

一句话结论

离线处理所有查询和操作,按时间顺序或特定顺序排序后用并查集;常见于动态连通性问题,把删除操作转化为逆序插入。

概念解释

  • 离线:先读所有操作和查询,再排序处理。
  • 删除转插入:逆序处理,删除变成插入。
  • 并查集:维护连通性。

原理流程

  1. 读所有操作和查询。
  2. 标记哪些边存在。
  3. 逆序处理:删除操作变成插入(加边)。
  4. 查询时用并查集判断连通性。

代码 / 图示

动态连通性问题:
  操作:加边、删边、查询连通
离线:
  逆序处理:删边 -> 加边
  查询:并查集判断连通

常见误区

  • 误区:离线并查集用路径压缩;正解:逆序插入不需要回滚,可以用路径压缩。
  • 误区:删除操作直接删;正解:逆序后删除变成插入。

追问 / 延伸

  • Q:离线并查集 vs 可撤销并查集? A:离线并查集逆序处理,可撤销并查集在线回滚。
  • Q:动态连通性在线怎么做? A:用 Link-Cut Tree 或动态图连通性,复杂。

02.11.4-008 可持久化数组

频率 ★★ | 难度 进阶

一句话结论

可持久化数组用可持久化线段树实现,每次修改生成新版本;支持查询任意历史版本的值;空间 O(q log n)。

概念解释

  • 可持久化线段树:保存历史版本。
  • 数组:线段树叶子节点即数组元素。
  • 查询:在指定版本上查叶子节点。

原理流程

  1. 初始版本:建树。
  2. 修改:更新叶子节点,生成新版本。
  3. 查询:在指定版本上查叶子节点。

代码 / 图示

可持久化数组 = 可持久化线段树
  叶子节点 = 数组元素
  修改叶子 = 生成新版本
  查询版本 = 在指定版本上查叶子

常见误区

  • 误区:可持久化数组用数组直接复制;正解:直接复制 O(n),用可持久化线段树 O(log n)。
  • 误区:可持久化数组空间 O(n);正解:O(q log n)。

追问 / 延伸

  • Q:可持久化数组用于什么? A:历史版本查询,如编辑器撤销。
  • Q:可持久化数组 vs 可撤销数组? A:可持久化保留所有历史,可撤销只回滚。

待整理清单

  • [ ] 可持久化 Trie
  • [ ] 线段树分治
  • [ ] 动态图连通性