CSP暑期集训 Day 01 - 并查集回顾 + ST表 + 倍增 + LCA

✏️

🧽

📎

📘 DAY 01

并查集 · ST表 · LCA

CSP 暑期集训 · 数据结构与倍增专题

🔗

并查集回顾

路径压缩 / 按秩合并 / 敌人关系

📊

ST表与倍增

RMQ问题 · O(nlogn)预处理 · O(1)查询

🌳

LCA倍增求法

最近公共祖先 · 树上倍增

📎

📍 问题场景：朋友圈合并
有 n 个人，初始时每个人各自独立。接下来给出 m 条信息："A和B是朋友"。朋友的朋友也是朋友。问：最终有多少个朋友圈？任意两人是否在同一朋友圈？

🤔 暴力做法 vs 并查集

❌ 暴力：每次合并后遍历

合并(A,B)：找到A所在集合所有元素，逐个加入B的集合
复杂度：O(n) 每次合并
m次合并：O(nm) → 超时！

✅ 并查集：用树表示集合

每个集合用一棵树表示，树的根就是集合的代表元素
合并：把一棵树的根连到另一棵树的根
复杂度：O(1) 每次合并（优化后）

💡 核心思想

用 fa[x] 数组表示：x 的父亲节点
• 如果 fa[x] == x，说明 x 是根节点（代表元素）
• Find(x)：从 x 往上爬，直到根节点 → 找到 x 所在集合的代表
• Union(x,y)：找到 x 的根 fx，找到 y 的根 fy，让 fa[fx] = fy（合并两棵树）

💡关键：并查集的核心是"找根"——同一个集合的所有元素，最终都指向同一个根节点！

🎯并查集 = 用树表示集合 + 用根节点代表集合 + 合并时连根

🧽

📝 基础并查集实现

const int MAXN = 10005;
int fa[MAXN];  // fa[x] 表示 x 的父亲节点

// 初始化：每个人各自独立，自己是自己的根
void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;  // 初始时，i 的根就是自己
    }
}

// 查找：找到 x 所在集合的根节点
int find(int x) {
    while (fa[x] != x) {  // 只要 x 不是根，就往上爬
        x = fa[x];        // x 变成父亲，继续往上
    }
    return x;  // 返回根节点
}

// 合并：把 x 和 y 所在的集合合并
void unite(int x, int y) {
    int fx = find(x);  // 找 x 的根
    int fy = find(y);  // 找 y 的根
    if (fx != fy) {     // 如果不在同一集合
        fa[fx] = fy;     // 把 fx 连到 fy 下面（合并）
    }
}

📊 图解：unite(1, 2) 的过程

初始状态

12

fa[1]=1, fa[2]=2

→

find(1)=1, find(2)=2

1 2

两个不同的根

→

fa[1] = 2

2

↑

1

1 的根变成 2

Find:O(n) 最坏

Unite:O(n) 最坏

优化后:O(α(n)) ≈ O(1)

💡问题：如果树退化成链状，find 会退化成 O(n)！
解决：路径压缩 + 按秩合并（下一页讲解）

✏️

📍 优化目标：让树更扁平，避免链状退化，使 find 接近 O(1)

🔧 优化一：路径压缩

思想：find 时把经过的节点都连到根

压缩前

1

↓

2

↓

3

↓

4

链状 O(n)

→

压缩后

1

2 3 4

扁平 O(1)

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);  // 递归压缩
}

🔧 优化二：按秩合并

思想：把矮树挂到高树下面

用 rnk[x] 记录 x 为根的树的高度（秩）
合并时：把秩小的根连到秩大的根下面
如果秩相同，合并后秩 +1

int fa[MAXN], rnk[MAXN];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        rnk[i] = 0;  // 初始高度为0
    }
}

void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (rnk[fx] < rnk[fy]) swap(fx, fy);
    fa[fy] = fx;  // 矮树挂到高树
    if (rnk[fx] == rnk[fy]) rnk[fx]++;
}

🎯路径压缩 + 按秩合并 → 复杂度 O(α(n)) ≈ O(1)，几乎不会退化！

💡易错点：① find 忘记路径压缩 ② 合并前忘记先 find ③ rnk 数组忘记初始化

📎

📋 题目描述

给定 n 个元素和 m 个操作，操作类型如下：
• 1 x y：合并 x 和 y 所在的集合
• 2 x y：查询 x 和 y 是否在同一集合，输出 "Y" 或 "N"

💡 思路分析

直接套用并查集模板！
• 操作1 → unite(x, y)
• 操作2 → 判断 find(x) == find(y)
注意：必须加路径压缩+按秩合并，否则会 TLE

📝 完整代码

#include <iostream>
using namespace std;

const int MAXN = 10005;
int fa[MAXN], rnk[MAXN];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        rnk[i] = 0;
    }
}

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);  // 路径压缩
}

void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (rnk[fx] < rnk[fy]) swap(fx, fy);
    fa[fy] = fx;
    if (rnk[fx] == rnk[fy]) rnk[fx]++;
}

int main() {
    int n, m;
    cin >> n >> m;
    init(n);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) unite(x, y);
        else cout << (find(x) == find(y) ? "Y" : "N") << "\n";
    }
    return 0;
}

时间复杂度:O(m·α(n))

空间复杂度:O(n)

✏️

📍 问题场景：区间最值查询（RMQ）
给定一个长度为 n 的数组 a，有 m 次查询，每次查询区间 [l, r] 内的最大值（或最小值）。如何高效处理？

🤔 不同做法的复杂度对比

❌ 暴力：每次遍历区间

查询 [l,r]：for循环遍历一遍
单次查询：O(n)
m次查询：O(nm) → TLE！

✅ ST表：预处理+O(1)查询

预处理所有 2^k 长度区间的最值
预处理：O(nlogn)
单次查询：O(1)
m次查询：O(m) 极快！

💡 核心思想：倍增覆盖 + 幂等性

关键观察：最大值满足幂等性：max(x, x) = x
所以区间 [l,r] 可以用两个重叠的 2^k 区间完全覆盖！
定义：st[j][i] = 从 i 开始，长度为 2^j 的区间的最大值
递推：st[j][i] = max(st[j-1][i], st[j-1][i + 2^(j-1)])

💡ST表 vs 线段树：ST表只能查询（不能修改），但查询速度 O(1) 比线段树 O(logn) 更快！

🎯ST表 = 预处理所有2^k区间 + 用两个重叠区间覆盖查询

🧽

🔧 预处理：构建 st 数组

const int MAXN = 100005, LOG = 17;
int st[LOG][MAXN];  // st[j][i] 表示从 i 开始，长度 2^j 的区间最大值

void build(int n, int a[]) {
    // j=0: 长度为1的区间，就是 a[i] 本身
    for (int i = 1; i <= n; i++) {
        st[0][i] = a[i];
    }
    // j=1,2,...: 长度为2,4,8,...的区间
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            // 从 i 开始，长度 2^j 的区间
            // 可以拆成两个长度 2^(j-1) 的区间
            st[j][i] = max(st[j-1][i], st[j-1][i + (1 << (j-1))]);
        }
    }
}

🔧 查询：O(1) 区间最值

int query(int l, int r) {
    // 找到最大的 k，使得 2^k <= 区间长度
    int k = log2(r - l + 1);
    // 用两个 2^k 区间覆盖 [l, r]
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

📊 图解：query(2, 7) 的覆盖过程

区间长度 = 7-2+1 = 6，k = floor(log2(6)) = 2，2^2 = 4

st[2][2]

覆盖 [2,3,4,5]

st[2][4]

覆盖 [4,5,6,7]

✅ 两个区间重叠覆盖 [2,7]，取 max 即可！

💡关键：log2 可以用预处理的 lg 数组加速，避免浮点运算！

📎

📝 优化：预处理 lg 数组

const int MAXN = 100005, LOG = 17;
int st[LOG][MAXN];
int lg[MAXN];  // lg[i] = floor(log2(i))

void init_lg() {
    lg[1] = 0;
    for (int i = 2; i < MAXN; i++) {
        lg[i] = lg[i/2] + 1;  // 递推求 log2
    }
}

📝 完整代码

void build(int n, int a[]) {
    for (int i = 1; i <= n; i++) st[0][i] = a[i];
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[j][i] = max(st[j-1][i], st[j-1][i + (1 << (j-1))]);
        }
    }
}

int query(int l, int r) {
    int k = lg[r - l + 1];  // 用预处理好的 lg 数组
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

📊 st 数组示例（n=8）

j	区间长度	st[j][1]	st[j][2]	st[j][3]	st[j][4]	...
0	1	a[1]	a[2]	a[3]	a[4]	...
1	2	max(a[1..2])	max(a[2..3])	max(a[3..4])	max(a[4..5])	...
2	4	max(a[1..4])	max(a[2..5])	max(a[3..6])	max(a[4..7])	...
3	8	max(a[1..8])	-	-	-	...

预处理:O(nlogn)

查询:O(1)

空间:O(nlogn)

💡易错点：① st 数组大小是 LOG×MAXN，别开反了 ② 查询时 r-(1<<k)+1 可能为负数 ③ lg 数组要预处理到 MAXN

✏️

📋 题目描述

给定一个长度为 n 的数组，有 m 次查询，每次查询区间 [l, r] 的最大值。
数据范围：n ≤ 10^5，m ≤ 10^6（注意：查询次数很大！）

💡 思路分析

标准 ST 表模板题！
• 预处理 st 数组 + lg 数组
• 每次查询 O(1) 返回结果
注意：m 很大，必须用 scanf/printf 或 fast IO，否则 TLE！

📝 完整代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100005, LOG = 17;
int st[LOG][MAXN], lg[MAXN];

void init_lg() {
    lg[1] = 0;
    for (int i = 2; i < MAXN; i++)
        lg[i] = lg[i/2] + 1;
}

void build(int n) {
    for (int i = 1; i <= n; i++) scanf("%d", &st[0][i]);
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            st[j][i] = max(st[j-1][i], st[j-1][i + (1 << (j-1))]);
}

int query(int l, int r) {
    int k = lg[r - l + 1];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

int main() {
    init_lg();
    int n, m;
    scanf("%d%d", &n, &m);
    build(n);
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }
    return 0;
}

预处理:O(nlogn)

查询:O(m)

🎯 问题场景

💬 家族聚会

家族族谱是一棵树。两个人 u 和 v 要聚会，想找一个长辈作为聚会地点——这个长辈要尽可能"近"（辈分尽可能低）。

这个"最近的共同长辈"就是 最近公共祖先 (Lowest Common Ancestor, LCA)。

📊 图解

🤔 怎么做？

暴力法：让 u 一步步往上走到根，记录路径；再让 v 往上走，第一个碰到的就是 LCA。
问题：每次查询 O(n)，查询多了就 TLE！
优化思路：能不能预处理一下，让查询更快？→ 倍增法

核心思想：预处理每个节点向上跳 2^k 步到达的祖先 fa[k][u]，查询时大步跳、小步调，O(log n) 完成一次 LCA 查询。

📐 预处理：DFS 计算 depth + fa 数组

// depth[u] = u 的深度（根为 1）
// fa[k][u] = u 向上跳 2^k 步到达的祖先

void dfs(int u, int f) {
    depth[u] = depth[f] + 1;
    fa[0][u] = f;  // 跳 2^0 = 1 步 = 父亲
    for (int k = 1; k < LOG; k++)
        fa[k][u] = fa[k-1][fa[k-1][u]];
        // 跳 2^k 步 = 先跳 2^(k-1) 步，再跳 2^(k-1) 步
    for (int v : adj[u])
        if (v != f) dfs(v, u);
}

🔍 查询 LCA(u, v)

步骤：
① 深度对齐：让深的节点先往上跳，直到 u、v 深度相同
② 特判：如果此时 u == v，LCA 就是 u
③ 同时上跳：从大步到小步，如果 fa[k][u] ≠ fa[k][v]，就同时跳
④ 最终答案：fa[0][u] 就是 LCA

💻 完整查询函数

int lca(int u, int v) {
    // 步骤1：深度对齐
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = LOG-1; k >= 0; k--)
        if (depth[u] - (1 << k) >= depth[v])
            u = fa[k][u];
    // 现在 depth[u] == depth[v]
    
    // 步骤2：特判
    if (u == v) return u;
    
    // 步骤3：同时上跳
    for (int k = LOG-1; k >= 0; k--)
        if (fa[k][u] != fa[k][v]) {
            u = fa[k][u];
            v = fa[k][v];
        }
    
    // 步骤4：再跳一步就是 LCA
    return fa[0][u];
}

📊 复杂度分析

预处理:O(n log n)

单次查询:O(log n)

✅ 记忆口诀："深的先跳到齐，特判相等不分离，大步小步一起跳，最后一步是答案"

📋 题目描述

给定一棵有根多叉树，请求出指定两个节点的最近公共祖先。
数据范围：n, q ≤ 5×10^5

📝 完整代码

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 500005, LOG = 20;
vector<int> adj[MAXN];
int depth[MAXN], fa[LOG][MAXN];

void dfs(int u, int f) {
    depth[u] = depth[f] + 1;
    fa[0][u] = f;
    for (int k = 1; k < LOG; k++)
        fa[k][u] = fa[k-1][fa[k-1][u]];
    for (int v : adj[u])
        if (v != f) dfs(v, u);
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = LOG-1; k >= 0; k--)
        if (depth[u] - (1 << k) >= depth[v])
            u = fa[k][u];
    if (u == v) return u;
    for (int k = LOG-1; k >= 0; k--)
        if (fa[k][u] != fa[k][v]) {
            u = fa[k][u]; v = fa[k][v];
        }
    return fa[0][u];
}

int main() {
    int n, q, root;
    scanf("%d%d%d", &n, &q, &root);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(root, 0);
    while (q--) {
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

预处理:O(n log n)

查询:O(q log n)

🎯 问题场景

💬 敌人与朋友

有 n 个动物，它们之间的关系是：同类或敌人。
已知：
• 同类的同类是同类
• 敌人的敌人是同类

给定若干条关系，判断某些说法是否矛盾。

🧠 建模思路

核心技巧：开 2倍的并查集空间！

• fa[1..n]：表示每个动物自己的集合
• fa[n+1..2n]：表示每个动物的"敌人集合"

操作规则：
• A 和 B 是同类：合并 A 与 B，合并 A+n 与 B+n
• A 和 B 是敌人：合并 A 与 B+n，合并 A+n 与 B
• 判断 A 和 B 是否同类：看 find(A) == find(B)

💻 核心代码

// n 个动物，开 2n 的并查集
int fa[MAXN * 2];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

// A 和 B 是同类
void union_same(int a, int b) {
    merge(a, b);        // A 和 B 合并
    merge(a + n, b + n); // A的敌人 和 B的敌人 合并
}

// A 和 B 是敌人
void union_enemy(int a, int b) {
    merge(a, b + n);     // A 和 B的敌人 合并
    merge(a + n, b);     // A的敌人 和 B 合并
}

📋 题目描述

动物王国有三类动物 A、B、C，构成食物链：A吃B，B吃C，C吃A。
给定 k 句话，判断假话数量。
• "1 x y"：x 和 y 是同类
• "2 x y"：x 吃 y
假话条件：与前面真话矛盾，或 x/y > n，或 x 吃 x。

💡 解题思路

开 3 倍空间！（因为有三类关系循环）
• fa[1..n]：同类集合
• fa[n+1..2n]：被捕食者集合（被"我"吃的）
• fa[2n+1..3n]：捕食者集合（吃"我"的）

📝 完整代码

#include <cstdio>
using namespace std;

const int MAXN = 50005;
int fa[MAXN * 3];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) fa[x] = y;
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int main() {
    int n, k, ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n * 3; i++) fa[i] = i;
    while (k--) {
        int d, x, y;
        scanf("%d%d%d", &d, & x, & y);
        if (x > n || y > n) { ans++; continue; }
        if (d == 1) { // x 和 y 同类
            if (same(x, y + n) || same(x, y + n * 2)) { ans++; continue; }
            merge(x, y);
            merge(x + n, y + n);
            merge(x + n * 2, y + n * 2);
        } else { // x 吃 y
            if (x == y || same(x, y) || same(x, y + n * 2)) { ans++; continue; }
            merge(x, y + n);        // x 与 y的捕食者 同类
            merge(x + n, y + n * 2); // x的被吃者 与 y的捕食者 同类
            merge(x + n * 2, y);    // x的捕食者 与 y 同类
        }
    }
    printf("%d\n", ans);
    return 0;
}

时间:O(k · α(n))

空间:O(3n)

📌 并查集

绿 P3367 并查集（模板）

绿 P1111 修复公路

📌 ST表

绿 P3865 ST表（模板）

蓝 P1816 忠诚

📌 LCA

蓝 P3379 最近公共祖先（模板）

橙 P1967 货车运输

橙 P1073 最优贸易

📌 种类并查集

橙 P2024 食物链

📌 综合提升

橙 P3225 矿场

蓝 P4391 [BOI2009] Radio

橙 P1522 牛的旅行

🔑 例题参考答案

P3367：直接套并查集模板，路径压缩+按秩合并
P3865：ST表模板，注意预处理 lg 数组避免 log 计算
P3379：LCA倍增法模板，注意 DFS 栈溢出可用 BFS 替代
P2024：开 3 倍空间，维护"同类/被吃/吃我"三个集合

🎓

✅ 必做（巩固基础）

P1991 无线通讯网（并查集+二分）

P1536 村村通（并查集）

P2136 我最倒霉（并查集）

P1346 双路排序（并查集）

⭐ 选做（能力提升）

P1197 消灭寄生虫（并查集维护）

P1440 求m区间内的最小值（单调队列）

P2820 局域网（最小生成树思想）

P1194 买礼物（并查集+贪心）

💭 思考题

1. 并查集路径压缩后，为什么均摊复杂度是 O(α(n))？
2. ST表能处理"动态修改+区间查询"吗？如果不能，怎么办？
3. LCA 除了倍增法，还有哪些方法？各自的优劣？
4. 种类并查集开 k 倍空间，k 取决于什么？

🎉 Day 01 学习完成！

并查集 · ST表 · LCA · 种类并查集

明天见！加油 💪

🔗 并查集 · 问题引入

🔗 并查集 · 核心代码

🔗 路径压缩 + 按秩合并

📝 例题：P3367 并查集

📊 ST表 · 问题引入

📊 ST表 · 预处理与查询

📊 ST表 · 完整实现

📝 例题：P3865 ST表

🌲 LCA · 最近公共祖先

🌲 LCA · 倍增法

🌲 LCA · 查询代码实现

📝 例题：P3379 最近公共祖先

🐺 种类并查集 · 敌人关系

📝 例题：P2024 食物链

📋 下午题单

📝 课后作业