# 📚 算法竞赛模板及核心讲义速查手册（完整全集·共44个）

---

## 第一部分：基础算法

### 1. 快速排序
- **模板题**：hlcoding 162. 快速排序
- **算法讲义**：分治思想。取中间值作为基准，通过双指针将小于等于和大于等于的数分到两侧，递归处理。
```cpp
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
```

---

### 2. 归并排序
- **模板题**：hlcoding 164. 归并排序
- **算法讲义**：分治思想。递归左右两半，利用双指针与辅助数组将两个有序序列合并。

```cpp
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
```

---

### 3. 整数二分算法
- **模板题**：hlcoding 161. 数的范围
- **算法讲义**：单调性区间划分。模板1找左边界（不加1），模板2找右边界（加1防死循环）。

```cpp
bool check(int x) {/* ... */}

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
```

---

### 4. 浮点数二分算法
- **模板题**：hlcoding 82. 数的三次方根
- **算法讲义**：根据精度 `eps` 不断折半逼近。

```cpp
bool check(double x) {/* ... */}

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}
```

---

## 第二部分：高精度计算

### 5. 高精度加法
- **模板题**：hlcoding 67. 高精度加法
- **算法讲义**：逆序存储模拟竖式加法，逢10进1。

```cpp
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}
```

---

### 6. 高精度减法
- **模板题**：hlcoding 68. 高精度减法
- **算法讲义**：模拟手工减法，注意借位与去除前导零。

```cpp
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
```

---

### 7. 高精度乘低精度
- **模板题**：hlcoding 69. 高精度乘法
- **算法讲义**：大整数乘单精度整数。

```cpp
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
```

---

### 8. 高精度除以低精度
- **模板题**：hlcoding 159. 高精度除法
- **算法讲义**：从高位到低位逐位去除，保留余数。

```cpp
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
```

---

## 第三部分：前缀和与差分

### 9. 一维前缀和
- **模板题**：hlcoding 166. 前缀和
- **算法讲义**：$\mathcal{O}(1)$ 区间求和。

```cpp
S[i] = a[1] + a[2] + ... + a[i];
sum = S[r] - S[l - 1];
```

---

### 10. 二维前缀和
- **模板题**：hlcoding 171. 子矩阵的和
- **算法讲义**：容斥原理求子矩阵和。

```cpp
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1];
```

---

### 11. 一维差分
- **模板题**：hlcoding 167. 差分
- **算法讲义**：$\mathcal{O}(1)$ 区间修改。

```cpp
B[l] += c, B[r + 1] -= c;
```

---

### 12. 二维差分
- **模板题**：hlcoding 917. 差分矩阵
- **算法讲义**：子矩阵整体加减。

```cpp
B[x1, y1] += c, B[x2 + 1, y1] -= c, B[x1, y2 + 1] -= c, B[x2 + 1, y2 + 1] += c;
```

---

## 第四部分：位运算与双指针

### 13. 位运算
- **模板题**：hlcoding 215. 二进制中1的个数
- **算法讲义**：获取某一位、lowbit 运算。

```cpp
int bit = n >> k & 1;
int lowbit(int n) { return n & -n; }
```

---

### 14. 双指针算法
- **模板题**：hlcoding 168, 169
- **算法讲义**：利用单调性降低复杂度。

```cpp
for (int i = 0, j = 0; i < n; i ++ ) {
    while (j < i && check(i, j)) j ++ ;
}
```

---

## 第五部分：离散化与区间合并

### 15. 离散化
- **模板题**：hlcoding 430. 区间和
- **算法讲义**：把稀疏大数映射到连续下标。

```cpp
vector<int> alls;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}
```

---

### 16. 区间合并
- **模板题**：hlcoding 908. 区间合并
- **算法讲义**：按左端点排序后合并重叠区间。

```cpp
void merge(vector<PII> &segs) {
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else ed = max(ed, seg.second);
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}
```

---

## 第六部分：数据结构

### 17. 单链表
- **模板题**：hlcoding 204. 单链表
- **算法讲义**：数组模拟链表。

```cpp
int head, e[N], ne[N], idx;
void init() { head = -1; idx = 0; }
void insert(int a) { e[idx] = a, ne[idx] = head, head = idx ++ ; }
```

---

### 18. 双链表
- **模板题**：hlcoding 206. 双链表
- **算法讲义**：左右双指针数组模拟。

```cpp
int e[N], l[N], r[N], idx;
void init() { r[0] = 1, l[1] = 0; idx = 2; }
void insert(int a, int x) {
    e[idx] = x; l[idx] = a; r[idx] = r[a];
    l[r[a]] = idx; r[a] = idx ++ ;
}
```

---

### 19. 栈与队列
- **模板题**：hlcoding 205, 498
- **算法讲义**：数组模拟栈与队列。
```cpp
int stk[N], tt = 0;
int q[N], hh = 0, tt = -1;
```

---

### 20. 单调栈
- **模板题**：hlcoding 909. 单调栈
- **算法讲义**：找左右侧最近更大/更小元素。
```cpp
int tt = 0;
for (int i = 1; i <= n; i ++ ) {
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}
```

---

### 21. 单调队列
- **模板题**：hlcoding 910. 滑动窗口
- **算法讲义**：维护窗口最值。
```cpp
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ) {
    while (hh <= tt && check_out(q[hh])) hh ++ ;
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}
```

---

### 22. KMP字符串
- **模板题**：hlcoding 911. KMP字符串
- **算法讲义**：高效字符串匹配。
```cpp
for (int i = 2, j = 0; i <= m; i ++ ) {
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}
```

---

### 23. Trie树
- **模板题**：hlcoding 912. Trie字符串统计
- **算法讲义**：前缀树。
```cpp
void insert(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i ++ ) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
```

---

### 24. 并查集
- **模板题**：hlcoding 499, 500
- **算法讲义**：集合合并与查询。
```cpp
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
```

---

### 25. 堆
- **模板题**：hlcoding 209, 2934
- **算法讲义**：完全二叉树维护最值。
```cpp
void down(int u) {
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) { swap(h[u], h[t]); down(t); }
}
```

---

### 26. 一般哈希与字符串哈希
- **模板题**：hlcoding 208, 207
- **算法讲义**：拉链法、进制哈希。
```cpp
typedef unsigned long long ULL;
ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
```

---

## 第七部分：搜索与图论

### 27. 树与图的遍历 (DFS / BFS)
- **模板题**：hlcoding 812, 761
- **算法讲义**：邻接表遍历。
```cpp
void dfs(int u) {
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
        if (!st[e[i]]) dfs(e[i]);
}
```

---

### 28. 拓扑排序
- **模板题**：hlcoding 848. 有向图的拓扑序列
- **算法讲义**：DAG 拓扑排序。
```cpp
// 入度为0入队，遍历出边减入度
```

---

### 29. 最短路算法 (Dijkstra / Bellman-Ford / SPFA / Floyd)
- **模板题**：hlcoding 486, 487, 497, 496, 494
- **算法讲义**：单源/多源最短路。
```cpp
// 堆优化 Dijkstra 核心
if (dist[j] > distance + w[i]) {
    dist[j] = distance + w[i];
    heap.push({dist[j], j});
}
```

---

### 30. 最小生成树 (Prim / Kruskal)
- **模板题**：hlcoding 492, 493
- **算法讲义**：无向图最小生成树。
```cpp
// Kruskal 核心
int a = find(edges[i].a), b = find(edges[i].b);
if (a != b) { p[a] = b; res += edges[i].w; }
```

---

### 31. 二分图匹配 (染色法 / 匈牙利算法)
- **模板题**：hlcoding 982, 2937
- **算法讲义**：判断二分图、最大匹配。
```cpp
bool find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true;
            if (match[j] == 0 || find(match[j])) { match[j] = x; return true; }
        }
    }
    return false;
}
```

---

## 第八部分：数学与数论

### 32. 试除法与线性筛素数
- **模板题**：hlcoding 380, 125, 184
- **算法讲义**：求素数、分解质因数。
```cpp
void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
```

---

### 33. 约数与欧几里得算法
- **模板题**：hlcoding 382, 124, 130
- **算法讲义**：GCD、求约数。
```cpp
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
```

---

### 34. 欧拉函数
- **模板题**：hlcoding 768, 769
- **算法讲义**：互质个数。
```cpp
int phi(int x) {
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
```

---

### 35. 快速幂与扩展欧几里得
- **模板题**：hlcoding 157, 767
- **算法讲义**：快速幂、ExGCD。
```cpp
int qmi(int m, int k, int p) {
    int res = 1 % p;
    while (k) {
        if (k & 1) res = (long long)res * m % p;
        m = (long long)m * m % p;
        k >>= 1;
    }
    return res;
}
```

---

### 36. 高斯消元与组合数
- **模板题**：hlcoding 2926, 244, 383, 2928, 766
- **算法讲义**：解线性方程组、组合数各类求法（递推、逆元、Lucas、高精度）。

---

### 37. 线性求逆元
- **模板题**：hlcoding 383 前置
- **算法讲义**：$\mathcal{O}(N)$ 线性预处理全体逆元。
```cpp
inv[1] = 1;
for (int i = 2; i <= n; i ++ ) inv[i] = (p - p / i) * inv[p % i] % p;
```

---

## 第九部分：博弈论

### 38. NIM 博弈与 SG 函数
- **模板题**：hlcoding 755, 893
- **算法讲义**：异或和判定、有向图游戏 SG 值与 mex 运算。

---

## 第十部分：动态规划与高级专题

### 39. 背包问题
- **算法讲义**：01背包、完全背包。
```cpp
for(int i = 1; i <= n; i ++ )
    for(int j = m; j >= v[i]; j -- )
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
```

---

### 40. 编辑距离
- **模板题**：hlcoding 101. 编辑距离
- **算法讲义**：增删改最少步数。
```cpp
int edit_distance(string a, string b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; i ++ ) dp[i][0] = i;
    for (int j = 0; j <= m; j ++ ) dp[0][j] = j;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            if (a[i - 1] == b[j - 1]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    return dp[n][m];
}
```

---

### 41. 最长回文子串
- **模板题**：hlcoding 17. 最长回文子串
- **算法讲义**：中心扩展法。
```cpp
string longestPalindrome(string s) {
    if (s.empty()) return "";
    int start = 0, max_len = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) l -- , r ++ ;
        if (r - l - 1 > max_len) { max_len = r - l - 1; start = l + 1; }
    };
    for (int i = 0; i < s.size(); i ++ ) {
        expand(i, i); expand(i, i + 1);
    }
    return s.substr(start, max_len);
}
```

---

### 42. 最长上升子序列 LIS
- **算法讲义**：二分优化 $\mathcal{O}(N \log N)$。
```cpp
int len = 0;
q[0] = -2e9;
for (int i = 1; i <= n; i ++ ) {
    int l = 0, r = len;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (q[mid] < a[i]) l = mid;
        else r = mid - 1;
    }
    len = max(len, r + 1);
    q[r + 1] = a[i];
}
```

---

### 43. 树的直径
- **算法讲义**：两次搜索或树形 DP 求树上最远两点。
```cpp
int ans = 0;
int dfs(int u) {
    st[u] = true;
    int d1 = 0, d2 = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        int d = dfs(j) + 1;
        if (d > d1) { d2 = d1; d1 = d; }
        else if (d > d2) { d2 = d; }
    }
    ans = max(ans, d1 + d2);
    return d1;
}
```

---

### 44. 最近公共祖先 LCA (倍增法)
- **算法讲义**：树上倍增查询祖先。

```cpp
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 500005; // 节点最大数量
const int LOGN = 20;     // 2^19 > 500000，足以覆盖深度

vector<int> adj[MAXN];   // 邻接表存树
int depth[MAXN];         // 记录每个节点的深度
int fa[MAXN][LOGN];      // fa[u][k] 表示节点 u 的第 2^k 个祖先

// 预处理 DFS：计算每个节点的深度，以及初始化 2^0 代祖先（即直接父节点）
void dfs(int u, int p) {
    depth[u] = depth[p] + 1;
    fa[u][0] = p; // u 的 2^0 (即第 1 个) 祖先是它的父节点 p

// 倍增核心递推：fa[u][k] = fa[fa[u][k - 1]][k - 1]
    for (int k = 1; k < LOGN; ++k) {
        if (fa[u][k - 1] != 0) {
            fa[u][k] = fa[fa[u][k - 1]][k - 1];
        }
    }

// 遍历子节点
    for (int v : adj[u]) {
        if (v != p) { // 防止往回搜父节点
            dfs(v, u);
        }
    }
}

// 查询 u 和 v 的最近公共祖先 (LCA)
int getLCA(int u, int v) {
    // 1. 确保 u 的深度大于等于 v 的深度，如果不是则交换
    if (depth[u] < depth[v]) {
        swap(u, v);
    }

// 2. 将 u 向上跳，使其与 v 处于同一深度
    for (int k = LOGN - 1; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = fa[u][k];
        }
    }

// 如果此时 u 和 v 已经是同一个节点，说明 v 就是原 u 的祖先，直接返回
    if (u == v) {
        return u;
    }

// 3. u 和 v 同时向上跳，逼近 LCA 的下一层
    for (int k = LOGN - 1; k >= 0; --k) {
        // 当两者的第 2^k 代祖先不相同时，说明 LCA 还在上面，两点同时往上跳
        if (fa[u][k] != fa[v][k]) {
            u = fa[u][k];
            v = fa[v][k];
        }
    }

// 4. 此时 u 和 v 的直接父节点就是它们的 LCA
    return fa[u][0];
}

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

int n, m, root;
    // 输入：节点总数 n，查询次数 m，根节点 root
    if (!(cin >> n >> m >> root)) return 0;

// 输入树的边 (n - 1 条边)
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

// 预处理倍增数组
    depth[0] = 0; // 哨兵深度
    dfs(root, 0);

// 处理 m 次查询
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        cout << getLCA(u, v) << "\n";
    }

return 0;
}
```

### 核心步骤解析：
1. **倍增状态定义**：`fa[u][k]` 表示节点 `u` 向上走 $2^k$ 步到达的祖先。
2. **状态转移方程**：`fa[u][k] = fa[fa[u][k - 1]][k - 1];`
   * 意思很直观：要跳 $2^k$ 步，可以先从 `u` 跳 $2^{k-1}$ 步到达中间节点 `mid = fa[u][k - 1]`，然后再从 `mid` 往上跳 $2^{k-1}$ 步。
3. **LCA 查询流程**：
   * 先把深度较深的节点往上跳，让两节点处于同一高度。
   * 如果此时重合了，它俩就是祖先关系、直接返回。
   * 否则，两个节点**同时**从最大步数（$2^{19}, 2^{18} \dots$）开始往上试探：如果跳 $2^k$ 步后两个节点不同（说明还没到 LCA，LCA 还在上面），就执行跳跃；如果跳完后会汇合或超越，则不能跳。
   * 最后循环结束时，两节点会停在各自 LCA 的**正下方**，它们的直接父节点 `fa[u][0]` 就是最终的 LCA。

📚 算法竞赛模板及核心讲义速查手册（完整全集·共44个）

第一部分：基础算法

1. 快速排序

模板题：hlcoding 162. 快速排序
算法讲义：分治思想。取中间值作为基准，通过双指针将小于等于和大于等于的数分到两侧，递归处理。

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

2. 归并排序

模板题：hlcoding 164. 归并排序
算法讲义：分治思想。递归左右两半，利用双指针与辅助数组将两个有序序列合并。

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

3. 整数二分算法

模板题：hlcoding 161. 数的范围
算法讲义：单调性区间划分。模板1找左边界（不加1），模板2找右边界（加1防死循环）。

bool check(int x) {/* ... */}

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

4. 浮点数二分算法

模板题：hlcoding 82. 数的三次方根
算法讲义：根据精度 eps 不断折半逼近。

bool check(double x) {/* ... */}

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

第二部分：高精度计算

5. 高精度加法

模板题：hlcoding 67. 高精度加法
算法讲义：逆序存储模拟竖式加法，逢10进1。

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}

6. 高精度减法

模板题：hlcoding 68. 高精度减法
算法讲义：模拟手工减法，注意借位与去除前导零。

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

7. 高精度乘低精度

模板题：hlcoding 69. 高精度乘法
算法讲义：大整数乘单精度整数。

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

8. 高精度除以低精度

模板题：hlcoding 159. 高精度除法
算法讲义：从高位到低位逐位去除，保留余数。

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

第三部分：前缀和与差分

9. 一维前缀和

模板题：hlcoding 166. 前缀和
算法讲义：$\mathcal{O}(1)$ 区间求和。

S[i] = a[1] + a[2] + ... + a[i];
sum = S[r] - S[l - 1];

10. 二维前缀和

模板题：hlcoding 171. 子矩阵的和
算法讲义：容斥原理求子矩阵和。

S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1];

11. 一维差分

模板题：hlcoding 167. 差分
算法讲义：$\mathcal{O}(1)$ 区间修改。

B[l] += c, B[r + 1] -= c;

12. 二维差分

模板题：hlcoding 917. 差分矩阵
算法讲义：子矩阵整体加减。

B[x1, y1] += c, B[x2 + 1, y1] -= c, B[x1, y2 + 1] -= c, B[x2 + 1, y2 + 1] += c;

第四部分：位运算与双指针

13. 位运算

模板题：hlcoding 215. 二进制中1的个数
算法讲义：获取某一位、lowbit 运算。

int bit = n >> k & 1;
int lowbit(int n) { return n & -n; }

14. 双指针算法

模板题：hlcoding 168, 169
算法讲义：利用单调性降低复杂度。

for (int i = 0, j = 0; i < n; i ++ ) {
    while (j < i && check(i, j)) j ++ ;
}

第五部分：离散化与区间合并

15. 离散化

模板题：hlcoding 430. 区间和
算法讲义：把稀疏大数映射到连续下标。

vector<int> alls;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

16. 区间合并

模板题：hlcoding 908. 区间合并
算法讲义：按左端点排序后合并重叠区间。

void merge(vector<PII> &segs) {
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else ed = max(ed, seg.second);
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}

第六部分：数据结构

17. 单链表

模板题：hlcoding 204. 单链表
算法讲义：数组模拟链表。

int head, e[N], ne[N], idx;
void init() { head = -1; idx = 0; }
void insert(int a) { e[idx] = a, ne[idx] = head, head = idx ++ ; }

18. 双链表

模板题：hlcoding 206. 双链表
算法讲义：左右双指针数组模拟。

int e[N], l[N], r[N], idx;
void init() { r[0] = 1, l[1] = 0; idx = 2; }
void insert(int a, int x) {
    e[idx] = x; l[idx] = a; r[idx] = r[a];
    l[r[a]] = idx; r[a] = idx ++ ;
}

19. 栈与队列

模板题：hlcoding 205, 498
算法讲义：数组模拟栈与队列。

int stk[N], tt = 0;
int q[N], hh = 0, tt = -1;

20. 单调栈

模板题：hlcoding 909. 单调栈
算法讲义：找左右侧最近更大/更小元素。

int tt = 0;
for (int i = 1; i <= n; i ++ ) {
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

21. 单调队列

模板题：hlcoding 910. 滑动窗口
算法讲义：维护窗口最值。

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ) {
    while (hh <= tt && check_out(q[hh])) hh ++ ;
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

22. KMP字符串

模板题：hlcoding 911. KMP字符串
算法讲义：高效字符串匹配。

for (int i = 2, j = 0; i <= m; i ++ ) {
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

23. Trie树

模板题：hlcoding 912. Trie字符串统计
算法讲义：前缀树。

void insert(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i ++ ) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

24. 并查集

模板题：hlcoding 499, 500
算法讲义：集合合并与查询。

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

25. 堆

模板题：hlcoding 209, 2934
算法讲义：完全二叉树维护最值。

void down(int u) {
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) { swap(h[u], h[t]); down(t); }
}

26. 一般哈希与字符串哈希

模板题：hlcoding 208, 207
算法讲义：拉链法、进制哈希。

typedef unsigned long long ULL;
ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }

第七部分：搜索与图论

27. 树与图的遍历 (DFS / BFS)

模板题：hlcoding 812, 761
算法讲义：邻接表遍历。

void dfs(int u) {
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
        if (!st[e[i]]) dfs(e[i]);
}

28. 拓扑排序

模板题：hlcoding 848. 有向图的拓扑序列
算法讲义：DAG 拓扑排序。

// 入度为0入队，遍历出边减入度

29. 最短路算法 (Dijkstra / Bellman-Ford / SPFA / Floyd)

模板题：hlcoding 486, 487, 497, 496, 494
算法讲义：单源/多源最短路。

// 堆优化 Dijkstra 核心
if (dist[j] > distance + w[i]) {
    dist[j] = distance + w[i];
    heap.push({dist[j], j});
}

30. 最小生成树 (Prim / Kruskal)

模板题：hlcoding 492, 493
算法讲义：无向图最小生成树。

// Kruskal 核心
int a = find(edges[i].a), b = find(edges[i].b);
if (a != b) { p[a] = b; res += edges[i].w; }

31. 二分图匹配 (染色法 / 匈牙利算法)

模板题：hlcoding 982, 2937
算法讲义：判断二分图、最大匹配。

bool find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true;
            if (match[j] == 0 || find(match[j])) { match[j] = x; return true; }
        }
    }
    return false;
}

第八部分：数学与数论

32. 试除法与线性筛素数

模板题：hlcoding 380, 125, 184
算法讲义：求素数、分解质因数。

void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

33. 约数与欧几里得算法

模板题：hlcoding 382, 124, 130
算法讲义：GCD、求约数。

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

34. 欧拉函数

模板题：hlcoding 768, 769
算法讲义：互质个数。

int phi(int x) {
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

35. 快速幂与扩展欧几里得

模板题：hlcoding 157, 767
算法讲义：快速幂、ExGCD。

int qmi(int m, int k, int p) {
    int res = 1 % p;
    while (k) {
        if (k & 1) res = (long long)res * m % p;
        m = (long long)m * m % p;
        k >>= 1;
    }
    return res;
}

36. 高斯消元与组合数

模板题：hlcoding 2926, 244, 383, 2928, 766
算法讲义：解线性方程组、组合数各类求法（递推、逆元、Lucas、高精度）。

37. 线性求逆元

模板题：hlcoding 383 前置
算法讲义：$\mathcal{O}(N)$ 线性预处理全体逆元。

inv[1] = 1;
for (int i = 2; i <= n; i ++ ) inv[i] = (p - p / i) * inv[p % i] % p;

第九部分：博弈论

38. NIM 博弈与 SG 函数

模板题：hlcoding 755, 893
算法讲义：异或和判定、有向图游戏 SG 值与 mex 运算。

第十部分：动态规划与高级专题

39. 背包问题

算法讲义：01背包、完全背包。

for(int i = 1; i <= n; i ++ )
    for(int j = m; j >= v[i]; j -- )
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

40. 编辑距离

模板题：hlcoding 101. 编辑距离
算法讲义：增删改最少步数。

int edit_distance(string a, string b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; i ++ ) dp[i][0] = i;
    for (int j = 0; j <= m; j ++ ) dp[0][j] = j;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            if (a[i - 1] == b[j - 1]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    return dp[n][m];
}

41. 最长回文子串

模板题：hlcoding 17. 最长回文子串
算法讲义：中心扩展法。

string longestPalindrome(string s) {
    if (s.empty()) return "";
    int start = 0, max_len = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) l -- , r ++ ;
        if (r - l - 1 > max_len) { max_len = r - l - 1; start = l + 1; }
    };
    for (int i = 0; i < s.size(); i ++ ) {
        expand(i, i); expand(i, i + 1);
    }
    return s.substr(start, max_len);
}

42. 最长上升子序列 LIS

算法讲义：二分优化 $\mathcal{O}(N \log N)$。

int len = 0;
q[0] = -2e9;
for (int i = 1; i <= n; i ++ ) {
    int l = 0, r = len;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (q[mid] < a[i]) l = mid;
        else r = mid - 1;
    }
    len = max(len, r + 1);
    q[r + 1] = a[i];
}

43. 树的直径

算法讲义：两次搜索或树形 DP 求树上最远两点。

int ans = 0;
int dfs(int u) {
    st[u] = true;
    int d1 = 0, d2 = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        int d = dfs(j) + 1;
        if (d > d1) { d2 = d1; d1 = d; }
        else if (d > d2) { d2 = d; }
    }
    ans = max(ans, d1 + d2);
    return d1;
}

44. 最近公共祖先 LCA (倍增法)

算法讲义：树上倍增查询祖先。

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 500005; // 节点最大数量
const int LOGN = 20;     // 2^19 > 500000，足以覆盖深度

vector<int> adj[MAXN];   // 邻接表存树
int depth[MAXN];         // 记录每个节点的深度
int fa[MAXN][LOGN];      // fa[u][k] 表示节点 u 的第 2^k 个祖先

// 预处理 DFS：计算每个节点的深度，以及初始化 2^0 代祖先（即直接父节点）
void dfs(int u, int p) {
    depth[u] = depth[p] + 1;
    fa[u][0] = p; // u 的 2^0 (即第 1 个) 祖先是它的父节点 p

    // 倍增核心递推：fa[u][k] = fa[fa[u][k - 1]][k - 1]
    for (int k = 1; k < LOGN; ++k) {
        if (fa[u][k - 1] != 0) {
            fa[u][k] = fa[fa[u][k - 1]][k - 1];
        }
    }

    // 遍历子节点
    for (int v : adj[u]) {
        if (v != p) { // 防止往回搜父节点
            dfs(v, u);
        }
    }
}

// 查询 u 和 v 的最近公共祖先 (LCA)
int getLCA(int u, int v) {
    // 1. 确保 u 的深度大于等于 v 的深度，如果不是则交换
    if (depth[u] < depth[v]) {
        swap(u, v);
    }

    // 2. 将 u 向上跳，使其与 v 处于同一深度
    for (int k = LOGN - 1; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = fa[u][k];
        }
    }

    // 如果此时 u 和 v 已经是同一个节点，说明 v 就是原 u 的祖先，直接返回
    if (u == v) {
        return u;
    }

    // 3. u 和 v 同时向上跳，逼近 LCA 的下一层
    for (int k = LOGN - 1; k >= 0; --k) {
        // 当两者的第 2^k 代祖先不相同时，说明 LCA 还在上面，两点同时往上跳
        if (fa[u][k] != fa[v][k]) {
            u = fa[u][k];
            v = fa[v][k];
        }
    }

    // 4. 此时 u 和 v 的直接父节点就是它们的 LCA
    return fa[u][0];
}

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, root;
    // 输入：节点总数 n，查询次数 m，根节点 root
    if (!(cin >> n >> m >> root)) return 0;

    // 输入树的边 (n - 1 条边)
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 预处理倍增数组
    depth[0] = 0; // 哨兵深度
    dfs(root, 0);

    // 处理 m 次查询
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        cout << getLCA(u, v) << "\n";
    }

    return 0;
}

核心步骤解析：

倍增状态定义：fa[u][k] 表示节点 u 向上走 $2^k$ 步到达的祖先。
状态转移方程：fa[u][k] = fa[fa[u][k - 1]][k - 1];
意思很直观：要跳 $2^k$ 步，可以先从 u 跳 $2^{k-1}$ 步到达中间节点 mid = fa[u][k - 1]，然后再从 mid 往上跳 $2^{k-1}$ 步。
LCA 查询流程：
先把深度较深的节点往上跳，让两节点处于同一高度。
如果此时重合了，它俩就是祖先关系、直接返回。
否则，两个节点同时从最大步数（$2^{19}, 2^{18} \dots$）开始往上试探：如果跳 $2^k$ 步后两个节点不同（说明还没到 LCA，LCA 还在上面），就执行跳跃；如果跳完后会汇合或超越，则不能跳。
最后循环结束时，两节点会停在各自 LCA 的正下方，它们的直接父节点 fa[u][0] 就是最终的 LCA。

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

CSP-J2026备战指南