第十五章高级数据结构¶

基础数据结构能解决大部分问题，但当问题规模达到 \(10^5\) 甚至 \(10^6\) 级别、且涉及区间操作和复杂查询时，就需要更高效的数据结构。本章介绍竞赛中最常用的几种高级数据结构，它们是大量中高难度题目的核心工具。

15.1 线段树（Segment Tree）¶

15.1.1 什么是线段树¶

线段树是一种基于分治思想的二叉树结构，用于高效处理区间查询和区间修改问题。每个节点代表一个区间，叶子节点代表单个元素。

graph TD
    subgraph 线段树结构示例 - 区间[1,8]
        A["[1,8] sum=36"] --> B["[1,4] sum=10"]
        A --> C["[5,8] sum=26"]
        B --> D["[1,2] sum=3"]
        B --> E["[3,4] sum=7"]
        C --> F["[5,6] sum=11"]
        C --> G["[7,8] sum=15"]
        D --> H["[1,1] val=1"]
        D --> I["[2,2] val=2"]
        E --> J["[3,3] val=3"]
        E --> K["[4,4] val=4"]
        F --> L["[5,5] val=5"]
        F --> M["[6,6] val=6"]
        G --> N["[7,7] val=7"]
        G --> O["[8,8] val=8"]
    end

核心性质：

树的高度为 \(O(\log n)\)
节点总数不超过 \(4n\)
每次操作的时间复杂度为 \(O(\log n)\)

15.1.2 线段树的结构¶

用数组存储线段树。对于下标为 \(i\) 的节点：

左儿子下标：\(2i\)
右儿子下标：\(2i + 1\)
区间 \([l, r]\) 的中点：\(mid = (l + r) / 2\)

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

const int MAXN = 100010;

int a[MAXN];       // 原始数组
long long tree[4 * MAXN];  // 线段树数组（4倍空间）

// 建树：递归地将区间信息汇总到父节点
// o: 当前节点编号, l: 区间左端点, r: 区间右端点
void build(int o, int l, int r) {
    if (l == r) {
        // 叶子节点：直接存储原始数组的值
        tree[o] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * o, l, mid);         // 递归建左子树
    build(2 * o + 1, mid + 1, r); // 递归建右子树
    tree[o] = tree[2 * o] + tree[2 * o + 1]; // 汇总：区间和
}

建树复杂度： \(O(n)\)，每个元素恰好被访问一次。

15.1.3 单点修改¶

将位置 \(p\) 的值修改为 \(v\)，需要更新从根到叶子路径上所有节点。

graph TD
    subgraph 单点修改 a[3]=10 的过程
        A["[1,8] 更新"] --> B["[1,4] 更新"]
        A --> C["[5,8] 不变"]
        B --> D["[1,2] 不变"]
        B --> E["[3,4] 更新"]
        E --> J["[3,3] 修改为10"]
        E --> K["[4,4] 不变"]
    end

// 单点修改：将位置 p 的值修改为 v
// o: 当前节点编号, l: 区间左端点, r: 区间右端点
void update(int o, int l, int r, int p, int v) {
    if (l == r) {
        // 到达叶子节点，直接修改
        tree[o] = v;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid)
        update(2 * o, l, mid, p, v);      // 目标在左半区间
    else
        update(2 * o + 1, mid + 1, r, p, v); // 目标在右半区间
    tree[o] = tree[2 * o] + tree[2 * o + 1]; // 回溯更新父节点
}

时间复杂度： \(O(\log n)\)，沿树高下降。

15.1.4 区间查询¶

查询区间 \([ql, qr]\) 的信息（如区间和）。核心思想：将查询区间分解为线段树上的若干完整节点。

graph TD
    subgraph 查询区间[3,6]
        A["[1,8] 不完全包含"] --> B["[1,4] 不完全包含"]
        A --> C["[5,8] 不完全包含"]
        B --> D["[1,2] 不相交→返回0"]
        B --> E["[3,4] 完全包含→返回7"]
        C --> F["[5,6] 完全包含→返回11"]
        C --> G["[7,8] 不相交→返回0"]
    end

// 区间查询：求 [ql, qr] 的区间和
long long query(int o, int l, int r, int ql, int qr) {
    // 情况1：当前区间与查询区间无交集
    if (ql > r || qr < l) return 0;
    // 情况2：当前区间完全被查询区间包含
    if (ql <= l && r <= qr) return tree[o];
    // 情况3：当前区间与查询区间部分重叠，需要递归两侧
    int mid = (l + r) / 2;
    return query(2 * o, l, mid, ql, qr) +
           query(2 * o + 1, mid + 1, r, ql, qr);
}

时间复杂度： \(O(\log n)\)。每次递归至少将区间缩小一半，最多访问 \(O(\log n)\) 个节点。

15.1.5 懒标记（Lazy Propagation）¶

当需要区间修改（如将区间 \([ql, qr]\) 所有元素加上 \(v\)）时，逐个修改叶子节点的效率为 \(O(n)\)。懒标记的核心思想：先在覆盖整个区间的节点上打标记，等到真正需要访问子节点时再下传。

graph TD
    subgraph 懒标记下传过程
        A["节点[1,8] 懒标记+=5"] -->|"下传"| B["左子[1,4] 懒标记+=5"]
        A -->|"下传"| C["右子[5,8] 懒标记+=5"]
        B -->|"下传"| D["叶子[1,1] 值+=5"]
        B -->|"下传"| E["叶子[2,2] 值+=5"]
    end

#include <cstdio>
using namespace std;

const int MAXN = 100010;

int a[MAXN];
long long tree[4 * MAXN];  // 线段树节点值
long long lazy[4 * MAXN];  // 懒标记数组

// 将懒标记下传给子节点
void pushdown(int o, int l, int r) {
    if (lazy[o] == 0) return;  // 没有标记，无需下传
    int mid = (l + r) / 2;
    // 左子节点：累加懒标记，更新节点值
    lazy[2 * o] += lazy[o];
    tree[2 * o] += lazy[o] * (mid - l + 1);
    // 右子节点：同理
    lazy[2 * o + 1] += lazy[o];
    tree[2 * o + 1] += lazy[o] * (r - mid);
    // 清除当前节点的懒标记
    lazy[o] = 0;
}

// 建树
void build(int o, int l, int r) {
    lazy[o] = 0;
    if (l == r) {
        tree[o] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * o, l, mid);
    build(2 * o + 1, mid + 1, r);
    tree[o] = tree[2 * o] + tree[2 * o + 1];
}

// 区间修改：将 [ql, qr] 中每个元素加上 v
void update(int o, int l, int r, int ql, int qr, long long v) {
    if (ql <= l && r <= qr) {
        // 当前区间完全被包含：打懒标记
        lazy[o] += v;
        tree[o] += v * (r - l + 1);
        return;
    }
    pushdown(o, l, r);  // 部分重叠时，先下传标记
    int mid = (l + r) / 2;
    if (ql <= mid) update(2 * o, l, mid, ql, qr, v);
    if (qr > mid) update(2 * o + 1, mid + 1, r, ql, qr, v);
    tree[o] = tree[2 * o] + tree[2 * o + 1];
}

// 区间查询
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[o];
    pushdown(o, l, r);  // 查询前也要下传标记
    int mid = (l + r) / 2;
    long long res = 0;
    if (ql <= mid) res += query(2 * o, l, mid, ql, qr);
    if (qr > mid) res += query(2 * o + 1, mid + 1, r, ql, qr);
    return res;
}

复杂度总结：

操作	时间复杂度	空间复杂度
建树	\(O(n)\)	\(O(n)\)
单点修改	\(O(\log n)\)	—
区间修改	\(O(\log n)\)	—
区间查询	\(O(\log n)\)	—

线段树的常见变体

最大/最小值线段树：将合并操作改为 max / min
乘法线段树：懒标记需要同时维护加法和乘法（注意乘法优先级）
权值线段树：以值域为下标构建，用于求第 \(k\) 大等
动态开点线段树：不预先建满，按需分配节点，适用于值域很大但操作很少的情况

15.2 树状数组（Binary Indexed Tree / Fenwick Tree）¶

15.2.1 lowbit 运算¶

树状数组的核心操作是 lowbit(x)，它取出 \(x\) 的二进制表示中最低位的 1。

\[\text{lowbit}(x) = x \mathbin{\&} (-x)\]

\(x\)	二进制	\(-x\)（补码）	\(\text{lowbit}(x)\)
6	0110	1010	0010 = 2
8	1000	1000	1000 = 8
12	1100	0100	0100 = 4

15.2.2 树状数组的结构¶

树状数组用一个数组 c[] 维护前缀信息。c[i] 管辖的区间由 lowbit(i) 决定：

c[i] 存储的是区间 \([i - \text{lowbit}(i) + 1, i]\) 的和

#include <cstdio>
using namespace std;

const int MAXN = 500010;

int n;
long long c[MAXN];  // 树状数组

// lowbit 运算
int lowbit(int x) {
    return x & (-x);
}

// 单点修改：将位置 x 的值加上 v
void add(int x, long long v) {
    for (int i = x; i <= n; i += lowbit(i))
        c[i] += v;
}

// 前缀查询：求 [1, x] 的区间和
long long sum(int x) {
    long long res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        res += c[i];
    return res;
}

// 区间查询：求 [l, r] 的区间和
long long range_sum(int l, int r) {
    return sum(r) - sum(l - 1);
}

时间复杂度：

操作	时间复杂度	说明
`add(x, v)`	\(O(\log n)\)	最多跳 \(\log n\) 次
`sum(x)`	\(O(\log n)\)	最多跳 \(\log n\) 次
建树	\(O(n \log n)\) 或 \(O(n)\)	逐个 add 或从底向上

15.2.3 差分树状数组¶

树状数组天然擅长单点修改 + 前缀查询。但如果需要区间修改 + 单点查询，可以利用差分数组的思想。

核心思路：维护差分数组 \(d[i] = a[i] - a[i-1]\)，则：

区间 \([l, r]\) 加 \(v\)：只需 \(d[l] += v\)，\(d[r+1] -= v\)
查询 \(a[i]\)：求 \(d[1] + d[2] + \cdots + d[i]\)（前缀和）

// 差分树状数组：区间修改 + 单点查询
const int MAXN = 500010;
int n;
long long c[MAXN];

int lowbit(int x) { return x & (-x); }

void add(int x, long long v) {
    for (int i = x; i <= n; i += lowbit(i))
        c[i] += v;
}

long long sum(int x) {
    long long res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        res += c[i];
    return res;
}

// 区间 [l, r] 加 v
void range_add(int l, int r, long long v) {
    add(l, v);
    add(r + 1, -v);
}

// 单点查询位置 x 的值
long long point_query(int x) {
    return sum(x);
}

树状数组 vs 线段树

树状数组：代码短（5-10行）、常数小、空间省，适合单点修改 + 前缀查询
线段树：功能更强大，支持区间修改、区间查询、维护更多信息（最大值、最小值等）
对于简单的区间求和问题，优先选择树状数组

15.3 并查集进阶¶

15.3.1 带权并查集¶

在普通并查集的基础上，给每条边附加一个权值（如距离、差值等）。d[x] 表示 \(x\) 到其父节点的关系值。

#include <cstdio>
using namespace std;

const int MAXN = 50010;

int fa[MAXN];   // 父节点
int d[MAXN];    // 到父节点的距离/权值

// 初始化
void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        d[i] = 0;
    }
}

// 查找根节点 + 路径压缩 + 权值更新
int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);      // 递归找到根节点
    d[x] += d[fa[x]];            // 累加到根的距离
    fa[x] = root;                // 路径压缩
    return root;
}

// 合并：已知 x 到 y 的权值为 w（如 x 比 y 大 w）
bool merge(int x, int y, int w) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return false;  // 已在同一集合
    fa[rx] = ry;
    d[rx] = d[y] + w - d[x];    // 计算 rx 到 ry 的权值
    return true;
}

// 查询：x 到 y 的权值差
// 前提：x 和 y 在同一集合中
int query(int x, int y) {
    return d[x] - d[y];
}

典型应用： 食物链问题（POJ 1182）、区间关系判断。

15.3.2 扩展域并查集¶

当元素之间存在多种关系（如敌对、友好）时，将每个元素扩展为多个"域"，每个域代表一种状态。

经典例子： 食物链问题中，将每个动物 \(x\) 扩展为 3 个域：

\(x\)：表示 \(x\) 本身（同类域）
\(x + n\)：表示 \(x\) 的捕食域（\(x\) 能吃的东西）
\(x + 2n\)：表示 \(x\) 的天敌域

#include <cstdio>
using namespace std;

const int MAXN = 50010 * 3;  // 三倍空间

int fa[MAXN];

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

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

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

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

// 食物链：n 只动物，k 句话
int solve(int n, int k) {
    init(n);
    int lie = 0;
    while (k--) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (x > n || y > n) { lie++; continue; }

        if (op == 1) { // x 和 y 是同类
            // 如果 x 吃 y 或 y 吃 x，则说谎
            if (same(x, y + n) || same(x, y + 2 * n)) {
                lie++;
            } else {
                merge(x, y);          // 同类
                merge(x + n, y + n);  // 同类的捕食对象也相同
                merge(x + 2 * n, y + 2 * n); // 天敌也相同
            }
        } else { // op == 2, x 吃 y
            // 如果 x 和 y 是同类，或 y 吃 x，则说谎
            if (same(x, y) || same(x, y + 2 * n)) {
                lie++;
            } else {
                merge(x, y + n);          // x 吃 y → x 与 y 的捕食域合并
                merge(x + n, y + 2 * n);  // y 的捕食域是 x 的天敌域
                merge(x + 2 * n, y);      // x 的天敌域与 y 合并
            }
        }
    }
    return lie;
}

15.4 ST 表（Sparse Table）¶

15.4.1 倍增思想¶

ST 表用于解决静态区间最值查询问题（不支持修改）。核心思想是倍增：预处理所有长度为 \(2^k\) 的区间的最值，查询时用两个长度为 \(2^k\) 的区间拼接出答案。

定义 \(f[i][k]\) 为从位置 \(i\) 开始、长度为 \(2^k\) 的区间的最大值：

\[f[i][k] = \max(f[i][k-1],\ f[i + 2^{k-1}][k-1])\]

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

const int MAXN = 100010;
const int LOG = 20;  // log2(MAXN)

int a[MAXN];
int f[MAXN][LOG];    // f[i][k]: [i, i+2^k-1] 的最大值
int Log[MAXN];       // 预处理 log2 值

// 预处理
void init(int n) {
    // 预处理 log2
    Log[1] = 0;
    for (int i = 2; i <= n; i++)
        Log[i] = Log[i / 2] + 1;

    // 初始化：长度为 1 的区间
    for (int i = 1; i <= n; i++)
        f[i][0] = a[i];

    // 倍增递推
    for (int k = 1; (1 << k) <= n; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            f[i][k] = max(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
        }
    }
}

// O(1) 查询 [l, r] 的最大值
int query(int l, int r) {
    int k = Log[r - l + 1];  // 区间长度对应的 k
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

复杂度：

操作	时间复杂度	空间复杂度
预处理	\(O(n \log n)\)	\(O(n \log n)\)
查询	\(O(1)\)	—

ST 表的局限

不支持修改操作：任何修改都需要重新预处理
适用于"多次查询、不修改"的场景（如区间最值、区间 GCD）
只能处理可重复贡献的问题（即 \(\text{op}(x, x) = x\)，如 \(\max\)、\(\min\)、\(\gcd\)），不适用于区间和

15.5 分块简介¶

分块是一种"以空间换时间"的思路：将数组分成若干大小为 \(B \approx \sqrt{n}\) 的块，每个块内预处理信息。

15.5.1 基本思想¶

整块操作：直接使用预处理的信息，\(O(1)\)
散块操作：暴力遍历，\(O(B)\)
总复杂度：\(O(n/B + B) = O(\sqrt{n})\)

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

const int MAXN = 100010;

int n, B;           // B 为块大小
int a[MAXN];        // 原始数组
int bel[MAXN];      // 每个位置属于哪个块
long long sum[MAXN]; // 每个块的区间和
int add_tag[MAXN];  // 每个块的懒标记（区间加法）

// 初始化分块
void init() {
    B = sqrt(n);
    for (int i = 1; i <= n; i++) {
        bel[i] = (i - 1) / B + 1;
        sum[bel[i]] += a[i];
    }
}

// 区间 [l, r] 每个元素加 v
void range_add(int l, int r, int v) {
    int bl = bel[l], br = bel[r];
    if (bl == br) {
        // 同一个块内，暴力修改
        for (int i = l; i <= r; i++) {
            a[i] += v;
            sum[bl] += v;
        }
        return;
    }
    // 左边散块
    for (int i = l; bel[i] == bl; i++) {
        a[i] += v;
        sum[bl] += v;
    }
    // 中间整块
    for (int b = bl + 1; b < br; b++)
        add_tag[b] += v;
    // 右边散块
    for (int i = r; bel[i] == br; i--) {
        a[i] += v;
        sum[br] += v;
    }
}

// 查询位置 x 的值
int point_query(int x) {
    return a[x] + add_tag[bel[x]];
}

分块的适用场景

分块的适用范围非常广泛，几乎所有能用线段树解决的问题都可以用分块实现
分块的常数比线段树大，但代码更灵活，适合一些线段树难以维护的复杂操作
时间复杂度通常为 \(O(n\sqrt{n})\)，介于暴力 \(O(n^2)\) 和线段树 \(O(n\log n)\) 之间

15.6 ACM Day11 练习题¶

本节提供 11 道练习题，涵盖本章介绍的高级数据结构。建议先独立完成再对答案。

题目列表¶

#	题号	题目	核心算法	平台
1	CF 1971G	XOUR	并查集	Codeforces
2	CF 1968F	Equal XOR Segments	前缀异或 + 二分	Codeforces
3	CF 1985H1	Maximize the Largest Component (Easy Version)	并查集	Codeforces
4	CF 1922D	Berserk Monsters	模拟 + 链表	Codeforces
5	CF 1994D	Funny Game	并查集 / 构造	Codeforces
6	CF 2020D	Connect the Dots	并查集	Codeforces
7	CF 1932F	Feed Cats	差分 + 线段树/单调栈	Codeforces
8	CF 2184E	Exquisite Array	线段树 / 贪心	Codeforces
9	AT library_practice_2_a	RSQ (Range Sum Query)	树状数组	AtCoder
10	P3870	[TJOI2009] 开关	线段树（懒标记）	洛谷
11	P1955	[NOI2015] 程序自动分析	离散化 + 并查集	洛谷

15.6.1 CF 1971G — 并查集应用¶

题意： 给定一个数组，支持合并操作和查询操作，判断两个位置的元素是否在同一集合中。

思路： 标准的并查集模板题。每次读入合并操作就 union，读入查询操作就 find 比较。

C++ 代码：

#include <cstdio>
using namespace std;

const int MAXN = 200010;

int fa[MAXN];

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

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

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        init(n);
        // 根据题意进行合并与查询
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            merge(i, x);
        }
        for (int i = 1; i <= n; i++)
            printf("%d%c", find(i), " \n"[i == n]);
    }
    return 0;
}

复杂度分析： 上面的 find 只做了路径压缩，单次操作均摊 \(O(\log n)\)，总复杂度 \(O(n \log n)\)；若再配合按秩（或按大小）合并，单次操作可达 \(O(\alpha(n))\)（\(\alpha\) 为阿克曼函数的反函数，近似常数）。竞赛中仅路径压缩通常已足够快。

15.6.2 CF 1968F — 前缀异或 + 二分¶

题意： 给定数组，多次查询区间 \([l, r]\)：能否把该区间分成 \(k > 1\) 段连续子段，使每一段的异或和都相等。

思路： 设前缀异或数组 \(p[i] = a_1 \oplus a_2 \oplus \cdots \oplus a_i\)（\(p[0] = 0\)）。

若 \(p[r] = p[l-1]\)（区间总异或为 0）：任取一个分割点分成两段，两段异或必相等，直接 YES。
否则每段异或值 \(x \neq 0\)，段数 \(k\) 必为奇数（偶数段异或起来总和应为 0，矛盾），且能分 \(k \ge 5\) 段就一定能分 3 段，所以只需判 3 段：要求存在 \(l \le i < j \le r-1\)，使 \(p[i] = p[r]\) 且 \(p[j] = p[l-1]\)。此时三段 \([l,i],\,[i+1,j],\,[j+1,r]\) 的异或都等于 \(p[r] \oplus p[l-1]\)。注意必须先出现 \(p[r]\)、再出现 \(p[l-1]\)，顺序不能颠倒。
用 map<int, vector<int>> 存每个前缀异或值出现的所有位置（天然有序），查询时二分：先找最小的 \(i \ge l\) 使 \(p[i] = p[r]\)，再找最小的 \(j > i\) 使 \(p[j] = p[l-1]\)，若 \(j \le r-1\) 则 YES。

C++ 代码：

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, q;
        scanf("%d%d", &n, &q);
        vector<int> a(n + 1), p(n + 1, 0);
        map<int, vector<int>> pos;
        pos[0].push_back(0);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            p[i] = p[i - 1] ^ a[i];
            pos[p[i]].push_back(i);
        }
        while (q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            if (p[r] == p[l - 1]) {
                // 总异或为 0：任取一个分割点，两段异或必相等
                printf("YES\n");
                continue;
            }
            // 否则只可能分成奇数段，判 3 段即可：
            // 需要 l <= i < j <= r-1，且 p[i] = p[r]，p[j] = p[l-1]（顺序不能颠倒）
            bool ok = false;
            auto &w = pos[p[r]];
            auto it = lower_bound(w.begin(), w.end(), l); // 第一个 >= l 且 p[i] = p[r] 的 i
            if (it != w.end() && *it <= r - 1) {
                int i = *it;
                auto &v = pos[p[l - 1]];
                auto it2 = upper_bound(v.begin(), v.end(), i); // 第一个 > i 且 p[j] = p[l-1] 的 j
                if (it2 != v.end() && *it2 <= r - 1) ok = true;
            }
            printf(ok ? "YES\n" : "NO\n");
        }
    }
    return 0;
}

常见坑：两个位置的先后顺序

判 3 段时容易写成"\(p[l-1]\) 与 \(p[r]\) 各自在 \([l, r-1]\) 内出现过就行"，这是错的——必须保证 \(p[r]\) 的出现位置在 \(p[l-1]\) 的出现位置之前。反例：前缀异或序列为 \(A,C,A,C,B,C,B\)（对应查询整段，\(p[l-1]=A\)，\(p[r]=B\)），\(A\) 和 \(B\) 都在区间内出现过，但 \(B\) 之后再无 \(A\)，实际无解。取"最小的 \(i\) 使 \(p[i]=p[r]\)"是安全的贪心：\(i\) 越小，给 \(j\) 留的空间越大。

复杂度分析： 预处理 \(O(n)\)，每次查询 \(O(\log n)\)，总复杂度 \(O((n + q) \log n)\)。

15.6.3 CF 1985H1 — 并查集统计连通块¶

题意： 给定网格，每个格子可以上下左右连通。问将某个空格子填上后，最多能连接多少个不同的连通块。

思路： 先用并查集统计所有连通块。对于每个空格子，检查其上下左右四个方向有多少个不同的连通块，取最大值。

C++ 代码：

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

const int MAXN = 1000010;
int n, m;
char grid[MAXN];
int fa[MAXN], sz[MAXN];

int id(int r, int c) { return r * m + c; }

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

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;
    fa[rx] = ry;
    sz[ry] += sz[rx];
}

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        init(n * m);
        for (int i = 0; i < n; i++)
            scanf("%s", grid + i * m);
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (grid[id(r, c)] == '.') continue;
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[id(nr, nc)] == '#')
                        merge(id(r, c), id(nr, nc));
                }
            }
        }
        int ans = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (grid[id(r, c)] == '#') continue;
                set<int> comps;
                int total = 1; // 当前格子自身
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[id(nr, nc)] == '#') {
                        int root = find(id(nr, nc));
                        if (comps.find(root) == comps.end()) {
                            comps.insert(root);
                            total += sz[root];
                        }
                    }
                }
                ans = max(ans, total);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

复杂度分析： 并查集操作 \(O(nm \cdot \alpha(nm))\)，遍历空格子 \(O(nm)\)，总复杂度 \(O(nm \cdot \alpha(nm))\)。

15.6.4 CF 1922D — 模拟与链表¶

题意： 有一排怪物，每个有攻击力和防御力。每一轮，如果相邻两个怪物能互相造成伤害（攻击力 > 对方防御力），则它们受到伤害被移除。模拟整个过程。

思路： 使用链表模拟。每轮检查哪些怪物会被移除，用链表快速跳过已移除的元素。注意使用"延迟删除"避免重复处理。

C++ 代码：

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

const int MAXN = 300010;
int a[MAXN], d[MAXN];
int L[MAXN], R[MAXN]; // 链表

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
        for (int i = 0; i <= n + 1; i++) {
            L[i] = i - 1;
            R[i] = i + 1;
        }
        set<int> alive;
        for (int i = 1; i <= n; i++) alive.insert(i);

        for (int round = 1; round <= n; round++) {
            set<int> to_remove;
            for (int i : alive) {
                int l = L[i], r = R[i];
                long long damage = 0;
                if (l >= 1 && a[l] > d[i]) damage += a[l];
                if (r <= n && a[r] > d[i]) damage += a[r];
                if (damage > 0) to_remove.insert(i);
            }
            printf("%d%c", (int)to_remove.size(), " \n"[round == n]);
            if (to_remove.empty()) {
                for (int j = round + 1; j <= n; j++)
                    printf("0%c", " \n"[j == n]);
                break;
            }
            for (int i : to_remove) {
                alive.erase(i);
                int l = L[i], r = R[i];
                R[l] = r;
                L[r] = l;
            }
        }
    }
    return 0;
}

复杂度分析： 每轮最多移除 \(O(n)\) 个怪物，总复杂度 \(O(n^2)\) 最坏，但实际均摊复杂度较好。

15.6.5 CF 1994D — 并查集与构造¶

题意： 给定 \(n\) 个点（初始无边）和数组 \(a\)。依次进行 \(n-1\) 次操作：第 \(x\) 次操作（\(x\) 从 1 编号到 \(n-1\)）要选择两个不同的点 \(u, v\)，满足 \(|a_u - a_v|\) 能被 \(x\) 整除，并在 \(u, v\) 之间连一条无向边。问能否使最终的图连通；若能，输出 "YES" 和每次操作所连的点对。

思路： 正着做不好贪心（\(x\) 小的时候条件宽松，\(x\) 大的时候条件苛刻），所以倒序确定每次操作的边：从 \(x = n-1\) 递减到 \(1\)。处理操作 \(x\) 时，图中恰有 \(x + 1\) 个连通分量（初始 \(n\) 个，之前每步各合并一次）。取每个分量的一个代表点，共 \(x+1\) 个数对 \(x\) 取模只有 \(x\) 种余数——由鸽巢原理必有两个代表点 \(a\) 值 \(\bmod\ x\) 同余，即 \(|a_u - a_v|\) 是 \(x\) 的倍数，且二者位于不同分量。给操作 \(x\) 连这条边并用并查集合并。因此答案恒为 YES。由于加边顺序不影响最终连通性，最后按操作编号 \(1 \ldots n-1\) 正序输出即可。

C++ 代码：

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

const int MAXN = 2010;
int fa[MAXN];

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

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        init(n);
        vector<long long> a(n + 1);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        vector<pair<int,int>> ans(n);  // ans[x]：操作 x 连的边
        // 倒序确定每次操作的边：处理操作 x 时图中恰有 x+1 个连通分量
        for (int x = n - 1; x >= 1; x--) {
            vector<int> rep;               // 每个连通分量取一个代表点
            vector<char> vis(n + 1, 0);
            for (int i = 1; i <= n; i++) {
                int r = find(i);
                if (!vis[r]) { vis[r] = 1; rep.push_back(i); }
            }
            // rep.size() == x + 1，而 mod x 只有 x 种余数，
            // 鸽巢原理：必有两个代表点的 a 值 mod x 同余
            vector<int> bucket(x, 0);      // 余数 -> 代表点编号
            for (int v : rep) {
                int rm = a[v] % x;
                if (bucket[rm]) {
                    ans[x] = {bucket[rm], v};       // |a_u - a_v| 是 x 的倍数
                    fa[find(bucket[rm])] = find(v); // 合并两个分量
                    break;
                }
                bucket[rm] = v;
            }
        }
        printf("YES\n");
        for (int x = 1; x <= n - 1; x++)  // 按操作编号正序输出
            printf("%d %d\n", ans[x].first, ans[x].second);
    }
    return 0;
}

为什么倒序一定可行

倒序处理时"分量个数恰为 \(x+1\)"是关键不变量：它比余数种数 \(x\) 多 1，鸽巢原理保证每一步都能找到合法的跨分量边，所以这道构造题的答案恒为 YES。小例子：\(n=2,\ a=\{1,2\}\)，只有操作 \(x=1\)，而 \(1 \bmod 1 = 2 \bmod 1 = 0\) 同余，连边 \((1,2)\) 即连通。

复杂度分析： 每个 \(x\) 扫描全部点找分量代表并入桶，\(O(n)\) 次 find；总复杂度 \(O(n^2 \alpha(n))\)，对 \(n \le 2000\) 绰绰有余。

15.6.6 CF 2020D — 并查集与等差数列连边¶

题意： 数轴上有 \(n\) 个点（编号 \(1 \sim n\)），初始互不相连。进行 \(m\) 次操作，第 \(i\) 次给出 \(a_i, d_i, k_i\)（\(1 \le d_i \le 10\)），把点 \(a_i,\ a_i+d_i,\ a_i+2d_i,\ \ldots,\ a_i+k_i \cdot d_i\) 两两连通。所有操作结束后，问这些点构成多少个连通分量。

思路： 关键约束是 \(d \le 10\)，可以按步长 \(d\) 分层处理。注意到把等差数列两两连通，等价于只把数列中相邻两项依次连起来。维护 ext[i][d] 表示"从点 \(i\) 出发、沿步长 \(d\) 至少还要向后连多少步"：

读入每个操作 \((a, d, k)\) 时，只需 ext[a][d] = max(ext[a][d], k)，不立即合并；
全部操作读完后，对每个 \(d\) 从小到大扫描位置 \(i\)：若 ext[i][d] > 0，则合并 \(i\) 与 \(i+d\)，并令 ext[i+d][d] = max(ext[i+d][d], ext[i][d] - 1) 把剩余步数向后传播；
最后统计 find(i) == i 的个数即连通分量数。

这样每个 \((i, d)\) 组合只被处理一次，避免了逐点重复合并。

C++ 代码：

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

const int MAXN = 200010;
const int MAXD = 11;
int fa[MAXN];
int ext[MAXN][MAXD];  // ext[i][d]：从点 i 出发沿步长 d 至少还要向后连多少步

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

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            for (int d = 1; d <= 10; d++) ext[i][d] = 0;
        }
        while (m--) {
            int a, d, k;
            scanf("%d%d%d", &a, &d, &k);
            ext[a][d] = max(ext[a][d], k);  // 只记录起点，稍后统一传播
        }
        // 按步长 d 分层传播：ext[i][d] > 0 说明 i 与 i+d 相连，
        // 且从 i+d 还要继续连 ext[i][d]-1 步
        for (int d = 1; d <= 10; d++)
            for (int i = 1; i + d <= n; i++)
                if (ext[i][d] > 0) {
                    merge(i, i + d);
                    ext[i + d][d] = max(ext[i + d][d], ext[i][d] - 1);
                }
        int comp = 0;
        for (int i = 1; i <= n; i++)
            if (find(i) == i) comp++;
        printf("%d\n", comp);
    }
    return 0;
}

样例验证

\(n=10\)，两次操作 \((1,2,4)\) 与 \((2,2,4)\)：前者连通 \(\{1,3,5,7,9\}\)，后者连通 \(\{2,4,6,8,10\}\)，共 2 个连通分量，与官方样例一致。

复杂度分析： 每次操作 \(O(1)\) 记录，传播阶段对每个 \((i, d)\) 组合各做一次合并判断，总复杂度 \(O((10n + m) \cdot \alpha(n))\)。空间 \(O(10n)\)。

15.6.7 CF 1932F — 差分与单调栈¶

题意： 在坐标轴上有一些区间，每个位置被覆盖的次数有一个上限。求最多能选多少个区间，使得所有位置都不超过其上限。

思路： 用差分数组维护每个位置被覆盖的次数。遍历区间，用贪心策略优先选择右端点小的区间（经典区间调度）。配合差分数组快速检查是否有位置超限。

C++ 代码：

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<int> l(m), r(m);
        for (int i = 0; i < m; i++)
            scanf("%d%d", &l[i], &r[i]);
        // 按右端点排序
        vector<int> order(m);
        for (int i = 0; i < m; i++) order[i] = i;
        sort(order.begin(), order.end(), [&](int a, int b) {
            return r[a] < r[b];
        });
        vector<int> diff(n + 2, 0);
        int ans = 0;
        for (int idx : order) {
            // 检查 [l[idx], r[idx]] 内是否有位置被覆盖超过 1 次
            bool ok = true;
            int cur = 0;
            for (int i = l[idx]; i <= r[idx]; i++) {
                cur += diff[i];
                if (cur >= 1) { ok = false; break; }
            }
            if (ok) {
                ans++;
                diff[l[idx]]++;
                diff[r[idx] + 1]--;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

复杂度分析： 暴力版 \(O(mn)\)，实际可用线段树优化到 \(O(m \log n)\)。

15.6.8 CF 2184E — 线段树 / 贪心¶

题意： 给定序列和一系列操作，每个操作修改区间值或查询区间最值，要求高效处理。

思路： 标准的线段树区间修改 + 区间查询问题。用懒标记维护区间加法。

C++ 代码：

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

const int MAXN = 200010;
const long long INF = 1e18;

long long tree[4 * MAXN], lazy[4 * MAXN];

void pushdown(int o) {
    if (lazy[o] == 0) return;
    tree[2 * o] += lazy[o]; lazy[2 * o] += lazy[o];
    tree[2 * o + 1] += lazy[o]; lazy[2 * o + 1] += lazy[o];
    lazy[o] = 0;
}

void update(int o, int l, int r, int ql, int qr, long long v) {
    if (ql <= l && r <= qr) {
        tree[o] += v; lazy[o] += v;
        return;
    }
    pushdown(o);
    int mid = (l + r) / 2;
    if (ql <= mid) update(2 * o, l, mid, ql, qr, v);
    if (qr > mid) update(2 * o + 1, mid + 1, r, ql, qr, v);
    tree[o] = max(tree[2 * o], tree[2 * o + 1]);
}

long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[o];
    pushdown(o);
    int mid = (l + r) / 2;
    long long res = -INF;
    if (ql <= mid) res = max(res, query(2 * o, l, mid, ql, qr));
    if (qr > mid) res = max(res, query(2 * o + 1, mid + 1, r, ql, qr));
    return res;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        long long x;
        scanf("%lld", &x);
        update(1, 1, n, i, i, x);
    }
    while (m--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            long long v;
            scanf("%lld", &v);
            update(1, 1, n, l, r, v);
        } else {
            printf("%lld\n", query(1, 1, n, l, r));
        }
    }
    return 0;
}

复杂度分析： 每次操作 \(O(\log n)\)，总复杂度 \(O((n + m) \log n)\)。

15.6.9 AT library_practice_2_a — 树状数组区间求和¶

题意： 实现一个数据结构，支持单点修改和区间求和（经典的 Range Sum Query）。

思路： 树状数组模板题。

C++ 代码：

#include <cstdio>
using namespace std;

const int MAXN = 500010;
int n;
long long c[MAXN];

int lowbit(int x) { return x & (-x); }

void add(int x, long long v) {
    for (int i = x; i <= n; i += lowbit(i))
        c[i] += v;
}

long long sum(int x) {
    long long res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        res += c[i];
    return res;
}

int main() {
    int q;
    scanf("%d%d", &n, &q);
    while (q--) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 0) {
            add(x, y);
        } else {
            printf("%lld\n", sum(y) - sum(x - 1));
        }
    }
    return 0;
}

复杂度分析： 每次操作 \(O(\log n)\)，总复杂度 \(O(q \log n)\)。

15.6.10 P3870 [TJOI2009] 开关¶

题意： 有一排 \(n\) 个灯泡，初始全关。每次操作将区间 \([l, r]\) 的灯泡状态翻转（开变关、关变开），或查询区间内有多少个灯泡是开着的。

思路： 用线段树维护区间内开着的灯泡数。懒标记表示"是否需要翻转"。下传时：

节点的值变为区间长度减去原值（\(tree[o] = len - tree[o]\)）
懒标记异或 1（两次翻转等于不翻转）

C++ 代码：

#include <cstdio>
using namespace std;

const int MAXN = 100010;

int tree[4 * MAXN];   // 区间内亮着的灯数
bool lazy[4 * MAXN];   // 是否需要翻转

void pushdown(int o, int l, int r) {
    if (!lazy[o]) return;
    int mid = (l + r) / 2;
    // 左子节点翻转
    tree[2 * o] = (mid - l + 1) - tree[2 * o];
    lazy[2 * o] = !lazy[2 * o];
    // 右子节点翻转
    tree[2 * o + 1] = (r - mid) - tree[2 * o + 1];
    lazy[2 * o + 1] = !lazy[2 * o + 1];
    lazy[o] = false;
}

void update(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        tree[o] = (r - l + 1) - tree[o];  // 翻转
        lazy[o] = !lazy[o];
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) update(2 * o, l, mid, ql, qr);
    if (qr > mid) update(2 * o + 1, mid + 1, r, ql, qr);
    tree[o] = tree[2 * o] + tree[2 * o + 1];
}

int query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[o];
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    int res = 0;
    if (ql <= mid) res += query(2 * o, l, mid, ql, qr);
    if (qr > mid) res += query(2 * o + 1, mid + 1, r, ql, qr);
    return res;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    while (m--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 0) {
            update(1, 1, n, l, r);
        } else {
            printf("%d\n", query(1, 1, n, l, r));
        }
    }
    return 0;
}

复杂度分析： 每次操作 \(O(\log n)\)，总复杂度 \(O(m \log n)\)。

15.6.11 P1955 [NOI2015] 程序自动分析¶

题意： 给定 \(n\) 个约束条件，分为"相等约束"和"不等约束"。判断所有约束是否可以同时满足。数据范围：\(t \le 10\) 组数据，每组 \(n \le 10^5\)，变量下标 \(i, j \le 10^9\)（下标很大，需要离散化）。

思路： 先处理所有"相等约束"（用并查集合并），再检查"不等约束"（如果两个元素在同一集合中，则矛盾）。由于元素值范围很大，需要先离散化。

C++ 代码：

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

const int MAXN = 200010 * 2;  // 每组 n <= 1e5，每个约束涉及 2 个变量，
                              // 离散化后单组至多 2n = 2e5 个变量，这里留了一倍裕量

int fa[MAXN];

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

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

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        vector<int> e1(n), e2(n), eq(n);
        vector<int> all_vals;
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", &e1[i], &e2[i], &eq[i]);
            all_vals.push_back(e1[i]);
            all_vals.push_back(e2[i]);
        }
        // 离散化
        sort(all_vals.begin(), all_vals.end());
        all_vals.erase(unique(all_vals.begin(), all_vals.end()), all_vals.end());
        auto get_id = [&](int x) {
            return lower_bound(all_vals.begin(), all_vals.end(), x) - all_vals.begin() + 1;
        };
        int m = all_vals.size();
        init(m);
        // 先处理相等约束
        for (int i = 0; i < n; i++) {
            if (eq[i] == 1) {
                merge(get_id(e1[i]), get_id(e2[i]));
            }
        }
        // 再检查不等约束
        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (eq[i] == 0) {
                if (find(get_id(e1[i])) == find(get_id(e2[i]))) {
                    ok = false;
                    break;
                }
            }
        }
        printf("%s\n", ok ? "YES" : "NO");
    }
    return 0;
}

复杂度分析： 离散化 \(O(n \log n)\)，并查集操作 \(O(n \cdot \alpha(n))\)，总复杂度 \(O(n \log n)\)。

本章小结¶

数据结构	核心操作	时间复杂度	适用场景
线段树	区间修改、区间查询	\(O(\log n)\)	通用区间操作
树状数组	单点修改、前缀查询	\(O(\log n)\)	简单区间和、计数
并查集	合并、查询集合	\(O(\alpha(n))\)	连通性、等价关系
ST 表	区间最值查询	\(O(1)\) 查询	静态区间最值
分块	区间操作	\(O(\sqrt{n})\)	通用、代码灵活

学习建议： 先掌握线段树和并查集（出现频率最高），再学习树状数组和 ST 表，最后了解分块。每种数据结构都要通过大量练习才能在比赛中熟练运用。

第十五章 高级数据结构¶

15.1 线段树（Segment Tree）¶

15.1.1 什么是线段树¶

15.1.2 线段树的结构¶

15.1.3 单点修改¶

15.1.4 区间查询¶

15.1.5 懒标记（Lazy Propagation）¶

15.2 树状数组（Binary Indexed Tree / Fenwick Tree）¶

15.2.1 lowbit 运算¶

15.2.2 树状数组的结构¶

15.2.3 差分树状数组¶

15.3 并查集进阶¶

15.3.1 带权并查集¶

15.3.2 扩展域并查集¶

15.4 ST 表（Sparse Table）¶

15.4.1 倍增思想¶

15.5 分块简介¶

15.5.1 基本思想¶

15.6 ACM Day11 练习题¶

题目列表¶

15.6.1 CF 1971G — 并查集应用¶

15.6.2 CF 1968F — 前缀异或 + 二分¶

15.6.3 CF 1985H1 — 并查集统计连通块¶

15.6.4 CF 1922D — 模拟与链表¶

15.6.5 CF 1994D — 并查集与构造¶

15.6.6 CF 2020D — 并查集与等差数列连边¶

15.6.7 CF 1932F — 差分与单调栈¶

15.6.8 CF 2184E — 线段树 / 贪心¶

15.6.9 AT library_practice_2_a — 树状数组区间求和¶

15.6.10 P3870 [TJOI2009] 开关¶

15.6.11 P1955 [NOI2015] 程序自动分析¶

本章小结¶

第十五章高级数据结构¶