# 基础算法模块讲义

本模块包含 **快速排序、归并排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并** 共 9 个核心基础算法。这些算法是算法竞赛和日常编程中的“基本功”。

---

## 1. 快速排序 (Quick Sort)

### 核心思想：分治法 (Divide and Conquer)
想象老师让你把全班同学按身高从矮到高排队。如果直接比会很慢，快速排序的聪明之处在于“分治”：
1. **找基准 ($x$)**：在数组中随便挑一个数字作为“基准数”（比如正中间的数）。
2. **分区 (Partition)**：调整数组，把所有**小于等于** $x$ 的数全赶到左边，把所有**大于等于** $x$ 的数全赶到右边。
3. **递归**：此时基准数已经落在了它最终排好队时的正确位置。接着用同样的方法处理左边的一群人和右边的一群人，直到整个数组有序。

### 双指针分区原理图解
定义两个指针 $i$ 和 $j$，分别从数组的最左端和最右端出发，向中间靠拢：
```
  l                 mid                 r
 [3]  5   1   2   [4]  6   8   7   9
  i                                 j
```
* $i$ 往右走，直到遇到一个 $\ge x$ 的数停下。
* $j$ 往左走，直到遇到一个 $\le x$ 的数停下。
* 交换 $i$ 和 $j$ 指向的数，然后继续，直到 $i$ 和 $j$ 相遇。

### C++ 代码模板
```cpp
void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[(l + r) >> 1], i = l - 1, j = 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. 归并排序 (Merge Sort)

### 核心思想：先分后合
* **分**：把一个长数组从中间切成两半，一直递归切到每个子区间只有 1 个数字（1个数字本身就是有序的）。
* **合（归并）**：把两个已经有序的小数组，合并成一个大有序数组。

### 归并过程数学图解
假设有两个有序数组 `[1, 3, 5]` 和 `[2, 4, 6]`：
```
[1, 3, 5]     [2, 4, 6]     -->     临时大盒子：[1, 2, 3, 4, 5, 6]
   ^             ^
指针 i         指针 j
```
* 比较 $i$ 和 $j$ 指向的数字，谁小就把谁先放入临时盒子，对应的指针往后移一位。

### C++ 代码模板
```cpp
int tmp[100010];

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. 二分 (Binary Search)

### 核心思想
玩“猜数字”游戏（1到100之间），每次猜中间数，根据“大了”或“小了”把范围砍掉一半。二分查找能把原本需要挨个找的 $O(n)$ 复杂度，直接降到 **$O(\log n)$**。

### 整数二分的两个核心模板
初中生最容易被二分的边界卡住。记住：**根据你的 `check` 条件决定怎么更新区间，选错模板会死循环**。

* **模板 1（找满足某种性质的右边界，常用于 `l = mid`, `r = mid - 1` 的对立情况）**：
```cpp
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1; // 注意这里一定要加 1
        if (check(mid)) l = mid;    // check 成立，说明答案在 [mid, r]
        else r = mid - 1;
    }
    return l;
}
```

* **模板 2（找满足某种性质的左边界）**：
```cpp
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;     // 这里不需要加 1
        if (check(mid)) r = mid;    // check 成立，说明答案在 [l, mid]
        else l = mid + 1;
    }
    return l;
}
```

---

## 4. 高精度 (High Precision)

### 核心原理
计算机里的 `int` 最大只能存约 $2 \times 10^9$，`long long` 也就 $9 \times 10^{18}$。如果要算 **100位数字 + 100位数字** 怎么办？
我们用**数组**来模拟小学列竖式计算的过程。

* **数组存数法**：把大数字的个位存在数组下标 `0` 的地方，十位存 `1`……
  例如数字 `12345` 存为：`vector<int> A = {5, 4, 3, 2, 1};`

### 高精度加法模板 (C++)
```cpp
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0; // 进位
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) 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;
}
```

---

## 5. 前缀和与差分 (Prefix Sum & Difference)

### 前缀和（秒算区间和）
* **定义**：前缀和数组 $S_i$ 表示原数组前 $i$ 个数字的总和。
  $$S_i = a_1 + a_2 + \dots + a_i$$
* **公式应用**：想求原数组从第 $L$ 个数到第 $R$ 个数的和？不需要循环，直接用：
  $$\text{Sum} = S_R - S_{L-1}$$
* **二维前缀和公式**：以 $(x_1, y_1)$ 为左上角、$(x_2, y_2)$ 为右下角的子矩阵和为：
  $$S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1]$$

### 差分（秒改区间值）
* **定义**：差分数组 $B$ 的前缀和就是原数组 $A$（即 $A$ 是 $B$ 的前缀和）。
* **神级应用**：如果要让原数组从第 $L$ 个数到第 $R$ 个数的每一个数都加上同一个常数 $c$，传统做法要循环 $R-L+1$ 次。**差分做法只需要两步**：
  $$B[L] += c, \quad B[R+1] -= c$$
  最后做一次前缀和还原，效率极高！

---

## 6. 双指针算法 (Two Pointers)

### 核心思想
用两个指针（比如下标 `i` 和 `j`）在数组或字符串上同步移动，把原本需要两层嵌套循环（$O(n^2)$）的暴力搜索，降维打击到线性时间复杂度 **$O(n)$**。

### 经典应用场景：最长连续不重复子序列
给定一个数组，求一个最长的连续区间，使得区间内部没有任何重复的数字。
```cpp
int j = 0;
for (int i = 0; i < n; i++) {
    count[a[i]]++; // 窗口右边界往右扩
    while (count[a[i]] > 1) { // 如果有重复，左边界往右缩，直到不重复
        count[a[j]]--;
        j++;
    }
    res = max(res, i - j + 1); // 记录最大长度
}
```

---

## 7. 位运算 (Bitwise Operations)

### 常用的 5 个基础符号
* `&` (按位与)：两位全为 1，结果才为 1。
* `|` (按位或): 有一个为 1，结果就为 1。
* `^` (异或): 相同为 0，不同为 1（**不进位的加法**。性质：$x \mathbin{\hat{}} x = 0$, $x \mathbin{\hat{}} 0 = x$）。
* `<<` (左移): 向左乘 2。
* `>>` (右移): 向右除 2。

### 核心神器：Lowbit
* **定义**：$\text{lowbit}(x)$ 返回 $x$ 的二进制表示中，**最低位的 1 及其后面的所有 0** 构成的数值。
* **数学公式**：
  $$\text{lowbit}(x) = x \& (-x)$$
* **例子**：若 $x = 10$（二进制 `1010`），最低位的 1 在第 2 位（从右往左数），$\text{lowbit}(10) = 2$（二进制 `10`）。
* **用途**：用来统计一个数字在二进制下有多少个 1。

---

## 8. 离散化 (Discretization)

### 核心思想
* **场景**：题目给你的坐标范围非常大（比如达到 $10^9$ 级别），但是涉及到的有效点非常少（比如只有 3000 个）。如果直接开一个 $10^9$ 大小的数组内存直接爆掉。
* **做法**：只保留数据之间的**相对大小关系**，把大数字“压缩”映射到较小的从 $0$ 或 $1$ 开始的连续整数编号。
* **实现三步曲**：
  1. 把所有需要用到的坐标存入数组并**排序**。
  2. 用 `unique` 函数**去重**。
  3. 用**二分查找 (`lower_bound`)** 查询某个大数字离散化之后对应的新编号。

---

## 9. 区间合并 (Interval Merging)

### 核心思想
给你一堆有交集的区间（例如 $[1, 3], [2, 6], [8, 10], [15, 18]$），把所有有重叠的区间合并成一个大区间。

### 算法步骤
1. 把所有区间按照**左端点**从小到大进行排序。
2. 维护当前正在合并的临时区间 $[st, ed]$。
3. 扫描后面的每个区间：
   * 如果后面区间的左端点 $\le ed$，说明有交集，更新当前区间的右边界：`ed = max(ed, next_ed)`。
   * 如果后面区间的左端点 $> ed$，说明断开了，把当前的 $[st, ed]$ 放入答案，然后更新 $[st, ed]$ 为新的区间。

---

基础算法模块讲义

本模块包含 快速排序、归并排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并 共 9 个核心基础算法。这些算法是算法竞赛和日常编程中的“基本功”。

1. 快速排序 (Quick Sort)

核心思想：分治法 (Divide and Conquer)

想象老师让你把全班同学按身高从矮到高排队。如果直接比会很慢，快速排序的聪明之处在于“分治”： 1. 找基准 ($x$)：在数组中随便挑一个数字作为“基准数”（比如正中间的数）。 2. 分区 (Partition)：调整数组，把所有小于等于 $x$ 的数全赶到左边，把所有大于等于 $x$ 的数全赶到右边。 3. 递归：此时基准数已经落在了它最终排好队时的正确位置。接着用同样的方法处理左边的一群人和右边的一群人，直到整个数组有序。

双指针分区原理图解

定义两个指针 $i$ 和 $j$，分别从数组的最左端和最右端出发，向中间靠拢：

  l                 mid                 r
 [3]  5   1   2   [4]  6   8   7   9
  i                                 j

$i$ 往右走，直到遇到一个 $\ge x$ 的数停下。
$j$ 往左走，直到遇到一个 $\le x$ 的数停下。
交换 $i$ 和 $j$ 指向的数，然后继续，直到 $i$ 和 $j$ 相遇。

C++ 代码模板

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[(l + r) >> 1], i = l - 1, j = 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. 归并排序 (Merge Sort)

核心思想：先分后合

分：把一个长数组从中间切成两半，一直递归切到每个子区间只有 1 个数字（1个数字本身就是有序的）。
合（归并）：把两个已经有序的小数组，合并成一个大有序数组。

归并过程数学图解

假设有两个有序数组 [1, 3, 5] 和 [2, 4, 6]：

[1, 3, 5]     [2, 4, 6]     -->     临时大盒子：[1, 2, 3, 4, 5, 6]
   ^             ^
指针 i         指针 j

比较 $i$ 和 $j$ 指向的数字，谁小就把谁先放入临时盒子，对应的指针往后移一位。

C++ 代码模板

int tmp[100010];

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. 二分 (Binary Search)

核心思想

玩“猜数字”游戏（1到100之间），每次猜中间数，根据“大了”或“小了”把范围砍掉一半。二分查找能把原本需要挨个找的 $O(n)$ 复杂度，直接降到 $O(\log n)$。

整数二分的两个核心模板

初中生最容易被二分的边界卡住。记住：根据你的 check 条件决定怎么更新区间，选错模板会死循环。

模板 1（找满足某种性质的右边界，常用于 l = mid, r = mid - 1 的对立情况）：

int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1; // 注意这里一定要加 1
        if (check(mid)) l = mid;    // check 成立，说明答案在 [mid, r]
        else r = mid - 1;
    }
    return l;
}

模板 2（找满足某种性质的左边界）：

int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;     // 这里不需要加 1
        if (check(mid)) r = mid;    // check 成立，说明答案在 [l, mid]
        else l = mid + 1;
    }
    return l;
}

4. 高精度 (High Precision)

核心原理

计算机里的 int 最大只能存约 $2 \times 10^9$，long long 也就 $9 \times 10^{18}$。如果要算 100位数字 + 100位数字 怎么办？我们用数组来模拟小学列竖式计算的过程。

数组存数法：把大数字的个位存在数组下标 0 的地方，十位存 1…… 例如数字 12345 存为：vector<int> A = {5, 4, 3, 2, 1};

高精度加法模板 (C++)

vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0; // 进位
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) 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;
}

5. 前缀和与差分 (Prefix Sum & Difference)

前缀和（秒算区间和）

定义：前缀和数组 $S_i$ 表示原数组前 $i$ 个数字的总和。 $$S_i = a_1 + a_2 + \dots + a_i$$
公式应用：想求原数组从第 $L$ 个数到第 $R$ 个数的和？不需要循环，直接用： $$\text{Sum} = S_R - S_{L-1}$$
二维前缀和公式：以 $(x_1, y_1)$ 为左上角、$(x_2, y_2)$ 为右下角的子矩阵和为： $$S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1]$$

差分（秒改区间值）

定义：差分数组 $B$ 的前缀和就是原数组 $A$（即 $A$ 是 $B$ 的前缀和）。
神级应用：如果要让原数组从第 $L$ 个数到第 $R$ 个数的每一个数都加上同一个常数 $c$，传统做法要循环 $R-L+1$ 次。差分做法只需要两步： $$B[L] += c, \quad B[R+1] -= c$$ 最后做一次前缀和还原，效率极高！

6. 双指针算法 (Two Pointers)

核心思想

用两个指针（比如下标 i 和 j）在数组或字符串上同步移动，把原本需要两层嵌套循环（$O(n^2)$）的暴力搜索，降维打击到线性时间复杂度 $O(n)$。

经典应用场景：最长连续不重复子序列

给定一个数组，求一个最长的连续区间，使得区间内部没有任何重复的数字。

int j = 0;
for (int i = 0; i < n; i++) {
    count[a[i]]++; // 窗口右边界往右扩
    while (count[a[i]] > 1) { // 如果有重复，左边界往右缩，直到不重复
        count[a[j]]--;
        j++;
    }
    res = max(res, i - j + 1); // 记录最大长度
}

7. 位运算 (Bitwise Operations)

常用的 5 个基础符号

& (按位与)：两位全为 1，结果才为 1。
| (按位或): 有一个为 1，结果就为 1。
^ (异或): 相同为 0，不同为 1（不进位的加法。性质：$x \mathbin{\hat{}} x = 0$, $x \mathbin{\hat{}} 0 = x$）。
<< (左移): 向左乘 2。
>> (右移): 向右除 2。

核心神器：Lowbit

定义：$\text{lowbit}(x)$ 返回 $x$ 的二进制表示中，最低位的 1 及其后面的所有 0 构成的数值。
数学公式： $$\text{lowbit}(x) = x \& (-x)$$
例子：若 $x = 10$（二进制 1010），最低位的 1 在第 2 位（从右往左数），$\text{lowbit}(10) = 2$（二进制 10）。
用途：用来统计一个数字在二进制下有多少个 1。

8. 离散化 (Discretization)

核心思想

场景：题目给你的坐标范围非常大（比如达到 $10^9$ 级别），但是涉及到的有效点非常少（比如只有 3000 个）。如果直接开一个 $10^9$ 大小的数组内存直接爆掉。
做法：只保留数据之间的相对大小关系，把大数字“压缩”映射到较小的从 $0$ 或 $1$ 开始的连续整数编号。
实现三步曲：
把所有需要用到的坐标存入数组并排序。
用 unique 函数去重。
用二分查找 (lower_bound) 查询某个大数字离散化之后对应的新编号。

9. 区间合并 (Interval Merging)

核心思想

给你一堆有交集的区间（例如 $[1, 3], [2, 6], [8, 10], [15, 18]$），把所有有重叠的区间合并成一个大区间。

算法步骤

把所有区间按照左端点从小到大进行排序。
维护当前正在合并的临时区间 $[st, ed]$。
扫描后面的每个区间：
如果后面区间的左端点 $\le ed$，说明有交集，更新当前区间的右边界：ed = max(ed, next_ed)。
如果后面区间的左端点 $> ed$，说明断开了，把当前的 $[st, ed]$ 放入答案，然后更新 $[st, ed]$ 为新的区间。

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