mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4mobile wallpaper 5mobile wallpaper 6mobile wallpaper 7mobile wallpaper 8mobile wallpaper 9mobile wallpaper 10mobile wallpaper 11mobile wallpaper 12mobile wallpaper 13
Profile Image of the Author
レム・咲く夜
LemuSakuya的个人博客网站堂堂登场
这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！
標籤
12705 字
33 分鐘
高级数据结构与图论
2026-06-03
Algorithm
Study Notes
/
Algorithm

第 11 章 高级数据结构与图论#

本章目标：理解线段树、树状数组、LCA、强连通分量、二分图匹配和网络流的核心模型。

11.1 学习目标#

  1. 掌握树状数组和线段树的适用范围。
  2. 掌握 LCA 的倍增思想。
  3. 了解强连通分量和缩点。
  4. 掌握二分图匹配建模。
  5. 理解最大流和最小割。

11.2 树状数组#

树状数组维护前缀信息，适用于满足可逆性的操作，如加法。

核心函数：

lowbit(x)=x&(−x)lowbit(x)=x\&(-x)

更新：

void add(int i, int delta) {
    for (; i <= n; i += i & -i) bit[i] += delta;
}

查询前缀和：

int sum(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) res += bit[i];
    return res;
}

复杂度：O(log⁡n)O(\log n)。

11.3 线段树#

线段树把区间递归拆成左右子区间。

适合：

  • 区间和。
  • 区间最大值。
  • 区间最小值。
  • 区间加法、赋值。
  • 区间查询 + 区间修改。

节点信息必须能由左右儿子合并：

info(parent)=merge(info(left),info(right))info(parent)=merge(info(left), info(right))

懒标记表示“这个区间整体已经更新，但还没下传给孩子”。

11.4 LCA 最近公共祖先#

倍增预处理：

up[u][k]=u 的 2k 级祖先up[u][k] = u \text{ 的 } 2^k \text{ 级祖先}

转移：

up[u][k]=up[up[u][k−1]][k−1]up[u][k]=up[up[u][k-1]][k-1]

查询时：

  1. 先把深度较大的点提升到同一深度。
  2. 从大到小尝试同时向上跳。
  3. 最后两点父亲就是 LCA。

复杂度：预处理 O(nlog⁡n)O(n\log n)，查询 O(log⁡n)O(\log n)。

11.5 强连通分量#

有向图中，如果 u 能到 v，v 也能到 u，则它们在同一个强连通分量中。

Tarjan 算法使用：

  • dfn[u]：访问时间。
  • low[u]：u 能回到的最早时间戳。
  • 栈：保存当前 DFS 路径上的点。

当 dfn[u]=low[u]dfn[u]=low[u] 时，u 是一个 SCC 的根。

缩点后图是 DAG，可做拓扑 DP。

11.6 二分图匹配#

二分图点集分为左右两部分，边只连接左右两侧。

最大匹配：选择最多互不共享端点的边。

增广路思想：如果存在一条从未匹配左点到未匹配右点的交替路径，就能让匹配数加一。

匈牙利算法复杂度常写为 O(nm)O(nm)。

11.7 网络流#

最大流模型：

  • 源点 s。
  • 汇点 t。
  • 每条边有容量 c。
  • 中间点满足流量守恒。

目标：最大化从 s 到 t 的总流量。

最大流最小割定理：

max⁡flow=min⁡cut\max flow = \min cut

Dinic 算法：

  1. BFS 建分层图。
  2. DFS 在分层图上增广。
  3. 重复直到汇点不可达。

11.8 建模建议#

问题信号可能模型
动态前缀和树状数组
区间修改查询线段树
树上路径祖先LCA
有向图互相可达SCC
配对问题二分图匹配
容量限制整体优化网络流
最少删除边断开最小割

11.9 易错点#

  1. 树状数组下标必须从 1 开始更方便。
  2. 线段树懒标记覆盖和加法混用错误。
  3. LCA 没处理根节点祖先。
  4. Tarjan 中栈内标记忘记取消。
  5. 二分图左右集合划分错误。
  6. 网络流反向边容量没维护。

11.10 练习#

  1. 用树状数组求逆序对。
  2. 写线段树支持区间加和区间和查询。
  3. 用倍增求树上 LCA。
  4. 用 Tarjan 求 SCC 并缩点。
  5. 用最大流解决二分图匹配。

ACM/OI 扩展：高阶模板：树链剖分、Dinic、SCC#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。 写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. 树状数组模板#

单点加、区间和。

template<class T>
struct BIT {
    int n;
    vector<T> t;
    BIT(int n = 0) { init(n); }
    void init(int n_) { n = n_; t.assign(n + 1, T{}); }
    void add(int i, T v) {
        for (; i <= n; i += i & -i) t[i] += v;
    }
    T sum(int i) const {
        T r{};
        for (; i > 0; i -= i & -i) r += t[i];
        return r;
    }
    T rangeSum(int l, int r) const { return sum(r) - sum(l - 1); }
};

要点：

  • 下标从 1 开始。
  • 区间加区间和需要两个 BIT。

2. 线段树区间加区间和#

最常见的 lazy propagation 模板。

struct SegTree {
    struct Node { long long sum = 0, lazy = 0; };
    int n;
    vector<Node> tr;
    SegTree(int n = 0): n(n), tr(4 * n + 5) {}
    void apply(int p, int l, int r, long long v) {
        tr[p].sum += v * (r - l + 1);
        tr[p].lazy += v;
    }
    void push(int p, int l, int r) {
        if (!tr[p].lazy || l == r) return;
        int m = (l + r) >> 1;
        apply(p << 1, l, m, tr[p].lazy);
        apply(p << 1 | 1, m + 1, r, tr[p].lazy);
        tr[p].lazy = 0;
    }
    void add(int p, int l, int r, int ql, int qr, long long v) {
        if (ql <= l && r <= qr) return apply(p, l, r, v);
        push(p, l, r);
        int m = (l + r) >> 1;
        if (ql <= m) add(p << 1, l, m, ql, qr, v);
        if (qr > m) add(p << 1 | 1, m + 1, r, ql, qr, v);
        tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
    }
    long long query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tr[p].sum;
        push(p, l, r);
        int m = (l + r) >> 1;
        long long ans = 0;
        if (ql <= m) ans += query(p << 1, l, m, ql, qr);
        if (qr > m) ans += query(p << 1 | 1, m + 1, r, ql, qr);
        return ans;
    }
};

要点：

  • apply 修改当前节点。
  • push 下传懒标记。
  • 多种标记混合时要定义组合顺序。

3. 树链剖分 HLD#

把树上路径拆成 O(log⁡n)O(\log n) 条重链，再用线段树维护。

path query complexity=O(log⁡2n)\text{path query complexity}=O(\log^2 n)

要点：

  • 第一次 DFS 求 size、depth、parent、heavy。
  • 第二次 DFS 求 top、dfn。
  • 路径查询时不断跳 top 深度更大的链。

4. Tarjan SCC#

有向图强连通分量，用于缩点成 DAG。

要点：

  • dfn[u] 是访问时间。
  • low[u] 是能回到的最早祖先。
  • 当 dfn[u]==low[u] 时弹栈形成一个 SCC。

常见坑：

  • 只对栈内点更新 low。
  • 弹栈后要取消 inStack。

5. Dinic 最大流模板结构#

最大流竞赛常用 Dinic。

struct Edge { int to, rev; long long cap; };
vector<vector<Edge>> g;
void addEdge(int u, int v, long long c) {
    Edge a{v, (int)g[v].size(), c};
    Edge b{u, (int)g[u].size(), 0};
    g[u].push_back(a); g[v].push_back(b);
}
// bfs 建 level，dfs 在分层图增广

要点：

  • 反向边必须存在。
  • 当前弧优化避免重复扫描。
  • 二分图匹配可以转成单位容量最大流。

训练题型：

  • 最大二分匹配。
  • 最小割建模。

本章模板背诵清单#

  • 能在 5 分钟内写出本章第一个核心模板。
  • 能说出每个模板的时间复杂度和空间复杂度。
  • 能说明模板不适用的反例。
  • 能为模板构造 3 个边界样例。
  • 能把模板改成 0-index 或 1-index 版本。

高级结构扩展#

可回滚并查集#

用于离线动态连通性、分治加边。

struct RollbackDSU {
    vector<int> p, sz;
    vector<pair<int,int>> stk;
    int comps;
    RollbackDSU(int n): p(n+1), sz(n+1,1), comps(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (x != p[x]) x = p[x]; return x; }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) { stk.push_back({-1,-1}); return false; }
        if (sz[a] < sz[b]) swap(a,b);
        p[b] = a; sz[a] += sz[b]; comps--;
        stk.push_back({a,b}); return true;
    }
    void rollback() {
        auto [a,b] = stk.back(); stk.pop_back();
        if (a == -1) return;
        sz[a] -= sz[b]; p[b] = b; comps++;
    }
};
  • 不能路径压缩，否则难回滚。
  • 按大小合并保证复杂度。
  • 每次 unite 都要入栈，包括无效合并。

主席树#

可持久化线段树，常用于静态区间第 k 小。

  • 每个前缀建一棵版本树。
  • 查询 [l,r] 用 root[r] - root[l-1]。
  • 每次插入只新建 O(log⁡n)O(\log n) 个节点。

动态开点线段树#

值域巨大但实际访问点少。

  • 节点按需创建。
  • 适合坐标到 10910^9 的区间修改查询。
  • 注意节点数量上限约为操作数乘 log 值域。

点分治#

树上路径统计的经典工具。

  • 每次找当前树重心。
  • 统计经过重心的路径贡献。
  • 删除重心后递归处理子树。
  • 复杂度通常 O(nlog⁡n)O(n\log n)。

最小费用最大流#

在最大流基础上，每条边有费用，目标是在指定流量下费用最小。

  • 常用 SPFA/Dijkstra + 势能找最短增广路。
  • 适合带匹配成本、运输成本的问题。
  • 数据通常比最大流小。

高频模板训练卡#

这一组训练卡用于把“11_高级数据结构与图论”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：树状数组#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 树状数组。
  • 优先模板：使用 树状数组 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 树状数组 写一道模板题，并记录 3 个实现坑。

卡 2：二维树状数组#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 二维树状数组。
  • 优先模板：使用 二维树状数组 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 二维树状数组 写一道模板题，并记录 3 个实现坑。

卡 3：线段树 lazy#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 线段树 lazy。
  • 优先模板：使用 线段树 lazy 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 线段树 lazy 写一道模板题，并记录 3 个实现坑。

卡 4：动态开点线段树#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 动态开点线段树。
  • 优先模板：使用 动态开点线段树 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 动态开点线段树 写一道模板题，并记录 3 个实现坑。

卡 5：主席树#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 主席树。
  • 优先模板：使用 主席树 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 主席树 写一道模板题，并记录 3 个实现坑。

卡 6：树链剖分#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 树链剖分。
  • 优先模板：使用 树链剖分 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 树链剖分 写一道模板题，并记录 3 个实现坑。

卡 7：点分治#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 点分治。
  • 优先模板：使用 点分治 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 点分治 写一道模板题，并记录 3 个实现坑。

卡 8：可回滚并查集#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 可回滚并查集。
  • 优先模板：使用 可回滚并查集 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 可回滚并查集 写一道模板题，并记录 3 个实现坑。

卡 9：SCC Tarjan#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 SCC Tarjan。
  • 优先模板：使用 SCC Tarjan 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 SCC Tarjan 写一道模板题，并记录 3 个实现坑。

卡 10：割点与桥#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 割点与桥。
  • 优先模板：使用 割点与桥 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 割点与桥 写一道模板题，并记录 3 个实现坑。

卡 11：二分图匹配#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 二分图匹配。
  • 优先模板：使用 二分图匹配 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 二分图匹配 写一道模板题，并记录 3 个实现坑。

卡 12：Dinic 最大流#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 Dinic 最大流。
  • 优先模板：使用 Dinic 最大流 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 Dinic 最大流 写一道模板题，并记录 3 个实现坑。

卡 13：最小割#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 最小割。
  • 优先模板：使用 最小割 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 最小割 写一道模板题，并记录 3 个实现坑。

卡 14：费用流#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 费用流。
  • 优先模板：使用 费用流 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 费用流 写一道模板题，并记录 3 个实现坑。

卡 15：欧拉序 + RMQ#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 欧拉序 + RMQ。
  • 优先模板：使用 欧拉序 + RMQ 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 欧拉序 + RMQ 写一道模板题，并记录 3 个实现坑。

卡 16：虚树#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 虚树。
  • 优先模板：使用 虚树 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 虚树 写一道模板题，并记录 3 个实现坑。

卡 17：DSU on Tree#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 DSU on Tree。
  • 优先模板：使用 DSU on Tree 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 DSU on Tree 写一道模板题，并记录 3 个实现坑。

卡 18：李超线段树#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 李超线段树。
  • 优先模板：使用 李超线段树 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 李超线段树 写一道模板题，并记录 3 个实现坑。

卡 19：平衡树 Treap#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 平衡树 Treap。
  • 优先模板：使用 平衡树 Treap 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 平衡树 Treap 写一道模板题，并记录 3 个实现坑。

卡 20：KD-Tree#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 KD-Tree。
  • 优先模板：使用 KD-Tree 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 KD-Tree 写一道模板题，并记录 3 个实现坑。

卡 21：可持久化 Trie#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 可持久化 Trie。
  • 优先模板：使用 可持久化 Trie 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 可持久化 Trie 写一道模板题，并记录 3 个实现坑。

卡 22：整体二分#

  • 题目信号：基础算法不足以维护动态区间、树上路径、连通变化或 整体二分。
  • 优先模板：使用 整体二分 模板，先确认维护的信息是否可合并。
  • 核心不变量：每次修改后，节点信息、懒标记或图残量网络保持合法。
  • 复杂度目标：通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。
  • 不适用场景：信息不可合并、需要在线删除但结构不支持时不适用。
  • 实现检查：检查数组空间、递归深度、懒标记组合、反向边、版本根。
  • 边界样例：单点、全区间、重复修改、空流量、不连通。
  • 训练题型：用 整体二分 写一道模板题，并记录 3 个实现坑。

本章赛前默写任务#

  • 默写 树状数组 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 二维树状数组 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 线段树 lazy 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 动态开点线段树 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 主席树 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 树链剖分 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 点分治 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 可回滚并查集 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 SCC Tarjan 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 默写 割点与桥 的模板，并写出 通常 O(log n)、O(log^2 n)、O(n log n) 或流算法复杂度。。
  • 为本章任选 3 个模板各写一个最小输入。
  • 为本章任选 3 个模板各写一个会使错误实现失败的反例。
  • 把本章所有模板整理到个人代码库，并标注 0-index / 1-index。

11_高级数据结构与图论：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：树状数组#

  • 识别信号：题面出现与“树状数组”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“树状数组”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：二维树状数组#

  • 识别信号：题面出现与“二维树状数组”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“二维树状数组”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：线段树#

  • 识别信号：题面出现与“线段树”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“线段树”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：懒标记#

  • 识别信号：题面出现与“懒标记”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“懒标记”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：动态开点#

  • 识别信号：题面出现与“动态开点”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“动态开点”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：主席树#

  • 识别信号：题面出现与“主席树”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“主席树”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：树链剖分#

  • 识别信号：题面出现与“树链剖分”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“树链剖分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：点分治#

  • 识别信号：题面出现与“点分治”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“点分治”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：可回滚并查集#

  • 识别信号：题面出现与“可回滚并查集”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“可回滚并查集”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：SCC#

  • 识别信号：题面出现与“SCC”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“SCC”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：割点桥#

  • 识别信号：题面出现与“割点桥”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“割点桥”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：二分图匹配#

  • 识别信号：题面出现与“二分图匹配”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“二分图匹配”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：Dinic#

  • 识别信号：题面出现与“Dinic”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“Dinic”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：最小割#

  • 识别信号：题面出现与“最小割”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“最小割”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：费用流#

  • 识别信号：题面出现与“费用流”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“费用流”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：虚树#

  • 识别信号：题面出现与“虚树”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“虚树”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：DSU on Tree#

  • 识别信号：题面出现与“DSU on Tree”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“DSU on Tree”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：李超线段树#

  • 识别信号：题面出现与“李超线段树”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“李超线段树”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：树状数组#

  • 识别信号：题面出现与“树状数组”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“树状数组”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：二维树状数组#

  • 识别信号：题面出现与“二维树状数组”相关的限制、操作或查询时，先判断能否套用本章模型。
  • 建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
  • 模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
  • 复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
  • 反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
  • 复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
  • 扩展任务：把“二维树状数组”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。
分享

如果這篇文章對你有幫助，歡迎分享給更多人！

高级数据结构与图论
https://lemusakuya.com/posts/study-notes/algorithm/11_高级数据结构与图论/
作者
レム・咲く夜
發布於
2026-06-03
許可協議
CC BY-NC-SA 4.0

部分資訊可能已經過時

数学算法与组合计数
综合训练 对拍 面试表达
相關文章 智能推薦
1
树与图论基础
Algorithm 《算法》学习笔记：07_树与图论基础
2
基础数据结构与语言工具
Algorithm 《算法》学习笔记：02_基础数据结构与语言工具
3
数学算法与组合计数
Algorithm 《算法》学习笔记：10_数学算法与组合计数
4
算法学习总览与复杂度分析
Algorithm 《算法》学习笔记：01_算法学习总览与复杂度分析
5
算法设计与分析完全学习手册
Algorithm 《算法》学习总览与学习路线
隨機文章 隨機推薦
1
反向传播 损失函数 优化算法
Neural Networks 2026-06-03
2
Markdown Extended Features
Examples 2024-05-01
3
Include Video in the Posts
Examples 2022-08-01
4
信息收集与OSINT
Cybersecurity 2026-04-27
5
图像复原与重建
Digital Image Processing 2026-04-27
© 2026 レム・咲く夜. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目錄