# GESP 九级编程能力认证完整讲义

## 第一模块：树状数组 (Fenwick Tree / BIT)
### 1. 知识点拆解
*   **本质**：利用整数二进制分解的特性，维护序列的前缀信息。
*   **核心操作**：
    *   `lowbit(x)`：返回 $x$ 二进制最低位的 $1$ 对应的值（`x & -x`）。
    *   **单点修改**：修改 $A[i]$，更新 $O(\log N)$ 个树状数组节点。
    *   **前缀查询**：查询 $Sum(1 \dots i)$，由 $O(\log N)$ 个区间合并而成。
*   **关联知识**：差分数组。配合差分可以实现“区间修改+单点查询”。

### 2. 具体例子
**例子 1.1**：求逆序对。
给定序列 `[5, 2, 3, 1]`，我们可以从左往右遍历，每遇到一个数 $x$，先查询树状数组中比 $x$ 大的数已经出现了多少次，然后将 $x$ 插入树状数组中。

### 3. 练习巩固
1.  **【单选题】** 树状数组执行一次单点更新操作的时间复杂度是（ ）。
    A. $O(1)$  B. $O(\log N)$  C. $O(\sqrt{N})$  D. $O(N)$
2.  **【对错题】** 树状数组可以用于求区间最大值，但前提是该序列必须是静态的，不支持在线修改。（ ）
3.  **【填空题】** 已知 `lowbit(x)` 函数，则 `lowbit(12)` 的结果是 ______，`lowbit(7)` 的结果是 ______。
4.  **【阅读程序填空】** 实现“区间修改，单点查询”：
    ```cpp
    void update(int x, int v) { // 修改差分序列
        for (; x <= n; x += x & -x) tree[x] += v;
    }
    // 给区间 [L, R] 增加 v
    update(L, v);
    update(________, -v);
    ```

---

## 第二模块：线段树 (Segment Tree) —— 懒标记体系
### 1. 知识点拆解
*   **结构**：平衡二叉树，每个节点维护一个区间 $[L, R]$。
*   **懒标记 (Lazy Tag)**：区间修改的核心。**“只给大区间打标记，不找子节点报到”**。只有当必须访问子节点时（`pushdown`），才下传标记。
*   **空间规则**：数组实现需开启 **$4N$** 空间。

### 2. 具体例子
**例子 2.1**：区间加法与区间求和。
当修改区间 $[1, 10]$ 全部加 $5$ 时，若当前节点正是 $[1, 10]$，则直接修改该节点的 `sum` 值并记录 `lazy += 5`，不再向下递归。

### 3. 练习巩固
1.  **【单选题】** 线段树在进行区间查询时，最多会将目标区间拆分成多少个子区间？
    A. $O(\log N)$  B. $O(N)$  C. $O(1)$  D. $O(N \log N)$
2.  **【对错题】** 线段树的 `pushdown` 操作应该在递归进入左右儿子之前执行。（ ）
3.  **【填空题】** 某线段树维护 $N=100$ 的序列，其根节点编号为 $1$，则节点 $10$ 的左儿子编号为 ______，右儿子编号为 ______。
4.  **【阅读程序填空】** 线段树下传标记函数：
    ```cpp
    void pushdown(int rt, int l, int r) {
        if (lazy[rt]) {
            int mid = (l + r) >> 1;
            lazy[rt << 1] += lazy[rt];
            tree[rt << 1] += (mid - l + 1) * lazy[rt];
            lazy[rt << 1 | 1] += lazy[rt];
            tree[rt << 1 | 1] += (________) * lazy[rt];
            lazy[rt] = 0;
        }
    }
    ```

---

## 第三模块：RMQ 与 ST 表 (Sparse Table)
### 1. 知识点拆解
*   **应用**：静态区间最值查询。
*   **倍增思想**：`f[i][j]` 表示从 $i$ 开始，长度为 $2^j$ 的区间内的最值。
*   **预处理**：$O(N \log N)$；**查询**：$O(1)$。
*   **限制**：不支持修改（一旦修改，预处理全部失效）。

### 2. 具体例子
**例子 3.1**：查询区间 $[3, 10]$ 的最大值。
区间长度为 $8$。我们只需要比较 `f[3][3]`（$[3, 3+2^3-1]$）即可得到答案。如果长度不是 $2$ 的幂，则取两块重叠的幂次区间取 `max`。

### 3. 练习巩固
1.  **【单选题】** ST 表查询的时间复杂度是 $O(1)$，这是因为它利用了最值问题的（ ）特性。
    A. 结合律  B. 交换律  C. 可重复贡献性（幂等性）  D. 分配律
2.  **【对错题】** 所有的区间问题（如区间和、区间最值、区间异或）都可以用 ST 表在 $O(1)$ 内查询。（ ）
3.  **【填空题】** 预处理 ST 表的递推式：`f[i][j] = max(f[i][j-1], f[i + (1 << (j-1))][j-1])`。其中 `(1 << (j-1))` 相当于计算 ______。

---

## 第四模块：强连通分量 (SCC) —— Tarjan 算法
### 1. 知识点拆解
*   **定义**：有向图中，若两个顶点互相可达，则称它们强连通。
*   **Tarjan 算法**：
    *   `dfn[u]`：进入 $u$ 的时间戳。
    *   `low[u]`：从 $u$ 出发能回溯到的最小时间戳。
*   **缩点 (Condensation)**：将每个 SCC 看作一个点，原图转化为 **DAG（有向无环图）**。这是解决图论难题的常用技巧。

### 2. 具体例子
**例子 4.1**：在一个有向图中寻找所有的环。
每个大小大于 $1$ 的 SCC 至少包含一个环。通过 Tarjan 找到 SCC 后，可以直接统计。

### 3. 练习巩固
1.  **【单选题】** 在 Tarjan 算法中，当满足以下哪个条件时，说明找到了一个强连通分量的根？
    A. `dfn[u] < low[u]`  B. `dfn[u] == low[u]`  C. `dfn[u] > low[u]`  D. `low[u] == 0`
2.  **【对错题】** 对有向图进行缩点后，得到的图一定是一个有向无环图（DAG）。（ ）
3.  **【填空题】** Tarjan 算法在运行过程中需要借助 ______（数据结构）来暂存当前搜索路径上的节点。
4.  **【阅读程序填空】** Tarjan 核心逻辑：
    ```cpp
    dfn[u] = low[u] = ++timer;
    stk.push(u); in_stk[u] = true;
    for (int v : edge[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (________) { // 已经在栈中
            low[u] = min(low[u], dfn[v]);
        }
    }
    ```

---

## 第五模块：树形动态规划 (Tree DP)
### 1. 知识点拆解
*   **特点**：在树上进行的 DP，通常采用 **DFS 后序遍历**（从叶子向上推）。
*   **状态设计**：通常为 `dp[u][0/1]`，表示以 $u$ 为根的子树，在 $u$ 点选或不选的情况下的最优解。
*   **典型问题**：没有上司的舞会（最大独立集）、树的重心、树的直径。

### 2. 具体例子
**例子 5.1**：没有上司的舞会。
每个节点有一个快乐值。如果选了父节点，就不能选子节点。
`dp[u][1] = val[u] + sum(dp[v][0])`（选 $u$，则子节点 $v$ 必不选）。
`dp[u][0] = sum(max(dp[v][0], dp[v][1]))`（不选 $u$，子节点 $v$ 可选可选不选）。

### 3. 练习巩固
1.  **【单选题】** 进行树形 DP 时，最常用的搜索方式是（ ）。
    A. 广度优先搜索 (BFS)  B. 深度优先搜索 (DFS)  C. 启发式搜索  D. 随机搜索
2.  **【对错题】** 树的重心是指：删除该点后，剩下的所有连通块中最大的一个规模最小。（ ）
3.  **【填空题】** 在求解“树的直径”（最长路径）时，可以通过两次 ______ 算法来实现（前提是边权为正）。
4.  **【阅读程序填空】** 树形 DP 转移片段：
    ```cpp
    void dfs(int u, int fa) {
        dp[u][0] = 0;
        dp[u][1] = happy[u];
        for (int v : edge[u]) {
            if (v == fa) continue;
            dfs(v, u);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += __________; 
        }
    }
    ```

---

## 教练参考答案

### 第一模块
1. B
2. 错（树状数组可以动态维护最值，但代码较复杂，一般用线段树替代）
3. 4；1
4. `update(R + 1, -v)`

### 第二模块
1. A
2. 对
3. 20；21
4. `r - mid`

### 第三模块
1. C
2. 错（只有满足幂等性的如 max/min/gcd 才行，区间和 sum 不行）
3. $2^{j-1}$

### 第四模块
1. B
2. 对
3. 栈 (Stack)
4. `in_stk[v]`

### 第五模块
1. B
2. 对
3. BFS 或 DFS
4. `dp[v][0]`

---
**教练寄语**：
九级的知识点逻辑密度极大。线段树和 Tarjan 是这级的两座大山。**学习建议**：不要死记硬背模板，尝试在纸上画出线段树的区间拆分图，或者手动模拟一遍 Tarjan 的入栈出栈过程。只要底层的“数据流”理通了，代码自然就顺了。加油！

GESP 九级编程能力认证完整讲义

第一模块：树状数组 (Fenwick Tree / BIT)

1. 知识点拆解

本质：利用整数二进制分解的特性，维护序列的前缀信息。
核心操作：
- lowbit(x)：返回 $x$ 二进制最低位的 $1$ 对应的值（x & -x）。
- 单点修改：修改 $A[i]$，更新 $O(\log N)$ 个树状数组节点。
- 前缀查询：查询 $Sum(1 \dots i)$，由 $O(\log N)$ 个区间合并而成。
关联知识：差分数组。配合差分可以实现“区间修改+单点查询”。

2. 具体例子

例子 1.1：求逆序对。给定序列 [5, 2, 3, 1]，我们可以从左往右遍历，每遇到一个数 $x$，先查询树状数组中比 $x$ 大的数已经出现了多少次，然后将 $x$ 插入树状数组中。

3. 练习巩固

【单选题】 树状数组执行一次单点更新操作的时间复杂度是（）。 A. $O(1)$ B. $O(\log N)$ C. $O(\sqrt{N})$ D. $O(N)$
【对错题】 树状数组可以用于求区间最大值，但前提是该序列必须是静态的，不支持在线修改。（）
【填空题】 已知 lowbit(x) 函数，则 lowbit(12) 的结果是 __，lowbit(7) 的结果是 ____。
【阅读程序填空】 实现“区间修改，单点查询”： cpp void update(int x, int v) { // 修改差分序列 for (; x <= n; x += x & -x) tree[x] += v; } // 给区间 [L, R] 增加 v update(L, v); update(________, -v);

第二模块：线段树 (Segment Tree) —— 懒标记体系

1. 知识点拆解

结构：平衡二叉树，每个节点维护一个区间 $[L, R]$。
懒标记 (Lazy Tag)：区间修改的核心。“只给大区间打标记，不找子节点报到”。只有当必须访问子节点时（pushdown），才下传标记。
空间规则：数组实现需开启 $4N$ 空间。

2. 具体例子

例子 2.1：区间加法与区间求和。当修改区间 $[1, 10]$ 全部加 $5$ 时，若当前节点正是 $[1, 10]$，则直接修改该节点的 sum 值并记录 lazy += 5，不再向下递归。

3. 练习巩固

【单选题】 线段树在进行区间查询时，最多会将目标区间拆分成多少个子区间？ A. $O(\log N)$ B. $O(N)$ C. $O(1)$ D. $O(N \log N)$
【对错题】 线段树的 pushdown 操作应该在递归进入左右儿子之前执行。（）
【填空题】 某线段树维护 $N=100$ 的序列，其根节点编号为 $1$，则节点 $10$ 的左儿子编号为 __，右儿子编号为 ____。
【阅读程序填空】 线段树下传标记函数： cpp void pushdown(int rt, int l, int r) { if (lazy[rt]) { int mid = (l + r) >> 1; lazy[rt << 1] += lazy[rt]; tree[rt << 1] += (mid - l + 1) * lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; tree[rt << 1 | 1] += (________) * lazy[rt]; lazy[rt] = 0; } }

第三模块：RMQ 与 ST 表 (Sparse Table)

1. 知识点拆解

应用：静态区间最值查询。
倍增思想：f[i][j] 表示从 $i$ 开始，长度为 $2^j$ 的区间内的最值。
预处理：$O(N \log N)$；查询：$O(1)$。
限制：不支持修改（一旦修改，预处理全部失效）。

2. 具体例子

例子 3.1：查询区间 $[3, 10]$ 的最大值。区间长度为 $8$。我们只需要比较 f[3][3]（$[3, 3+2^3-1]$）即可得到答案。如果长度不是 $2$ 的幂，则取两块重叠的幂次区间取 max。

3. 练习巩固

【单选题】 ST 表查询的时间复杂度是 $O(1)$，这是因为它利用了最值问题的（）特性。 A. 结合律 B. 交换律 C. 可重复贡献性（幂等性） D. 分配律
【对错题】 所有的区间问题（如区间和、区间最值、区间异或）都可以用 ST 表在 $O(1)$ 内查询。（）
【填空题】 预处理 ST 表的递推式：f[i][j] = max(f[i][j-1], f[i + (1 << (j-1))][j-1])。其中 (1 << (j-1)) 相当于计算 ______。

第四模块：强连通分量 (SCC) —— Tarjan 算法

1. 知识点拆解

定义：有向图中，若两个顶点互相可达，则称它们强连通。
Tarjan 算法：
- dfn[u]：进入 $u$ 的时间戳。
- low[u]：从 $u$ 出发能回溯到的最小时间戳。
缩点 (Condensation)：将每个 SCC 看作一个点，原图转化为 DAG（有向无环图）。这是解决图论难题的常用技巧。

2. 具体例子

例子 4.1：在一个有向图中寻找所有的环。每个大小大于 $1$ 的 SCC 至少包含一个环。通过 Tarjan 找到 SCC 后，可以直接统计。

3. 练习巩固

【单选题】 在 Tarjan 算法中，当满足以下哪个条件时，说明找到了一个强连通分量的根？ A. dfn[u] < low[u] B. dfn[u] == low[u] C. dfn[u] > low[u] D. low[u] == 0
【对错题】 对有向图进行缩点后，得到的图一定是一个有向无环图（DAG）。（）
【填空题】 Tarjan 算法在运行过程中需要借助 ______（数据结构）来暂存当前搜索路径上的节点。
【阅读程序填空】 Tarjan 核心逻辑： cpp dfn[u] = low[u] = ++timer; stk.push(u); in_stk[u] = true; for (int v : edge[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (________) { // 已经在栈中 low[u] = min(low[u], dfn[v]); } }

第五模块：树形动态规划 (Tree DP)

1. 知识点拆解

特点：在树上进行的 DP，通常采用 DFS 后序遍历（从叶子向上推）。
状态设计：通常为 dp[u][0/1]，表示以 $u$ 为根的子树，在 $u$ 点选或不选的情况下的最优解。
典型问题：没有上司的舞会（最大独立集）、树的重心、树的直径。

2. 具体例子

例子 5.1：没有上司的舞会。每个节点有一个快乐值。如果选了父节点，就不能选子节点。 dp[u][1] = val[u] + sum(dp[v][0])（选 $u$，则子节点 $v$ 必不选）。 dp[u][0] = sum(max(dp[v][0], dp[v][1]))（不选 $u$，子节点 $v$ 可选可选不选）。

3. 练习巩固

【单选题】 进行树形 DP 时，最常用的搜索方式是（）。 A. 广度优先搜索 (BFS) B. 深度优先搜索 (DFS) C. 启发式搜索 D. 随机搜索
【对错题】 树的重心是指：删除该点后，剩下的所有连通块中最大的一个规模最小。（）
【填空题】 在求解“树的直径”（最长路径）时，可以通过两次 ______ 算法来实现（前提是边权为正）。
【阅读程序填空】 树形 DP 转移片段： cpp void dfs(int u, int fa) { dp[u][0] = 0; dp[u][1] = happy[u]; for (int v : edge[u]) { if (v == fa) continue; dfs(v, u); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += __________; } }

教练参考答案

第一模块

B
错（树状数组可以动态维护最值，但代码较复杂，一般用线段树替代）
4；1
update(R + 1, -v)

第二模块

A
对
20；21
r - mid

第三模块

C
错（只有满足幂等性的如 max/min/gcd 才行，区间和 sum 不行）
$2^{j-1}$

第四模块

B
对
栈 (Stack)
in_stk[v]

第五模块

B
对
BFS 或 DFS
dp[v][0]

教练寄语：九级的知识点逻辑密度极大。线段树和 Tarjan 是这级的两座大山。学习建议：不要死记硬背模板，尝试在纸上画出线段树的区间拆分图，或者手动模拟一遍 Tarjan 的入栈出栈过程。只要底层的“数据流”理通了，代码自然就顺了。加油！

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

GESP 九级编程能力认证讲义

GESP 九级编程能力认证完整讲义

第一模块：树状数组 (Fenwick Tree / BIT)

1. 知识点拆解

2. 具体例子

3. 练习巩固

第二模块：线段树 (Segment Tree) —— 懒标记体系

1. 知识点拆解

2. 具体例子

3. 练习巩固

第三模块：RMQ 与 ST 表 (Sparse Table)

1. 知识点拆解

2. 具体例子

3. 练习巩固

第四模块：强连通分量 (SCC) —— Tarjan 算法

1. 知识点拆解

2. 具体例子

3. 练习巩固

第五模块：树形动态规划 (Tree DP)

1. 知识点拆解

2. 具体例子

3. 练习巩固

教练参考答案

第一模块

第二模块

第三模块

第四模块

第五模块