第十八章：分治与倍增——拆解与跳跃的智慧¶
你好！欢迎来到第十八章！在前面的章节，我们学习了递归、二分查找等算法。这一章我们将学习两种更强大的思想：分治和倍增。分治就像“分而治之”，把大问题拆成小问题解决；倍增就像“一步跨两级”，利用已知信息快速跳跃。掌握它们，你就能解决更多有趣的问题！
18.1 分治算法¶
18.1.1 什么是分治？¶
分治（Divide and Conquer）就是把一个复杂的大问题，分解成若干个相同或相似的子问题，再把子问题分解成更小的子问题……直到最后子问题可以直接求解，然后合并子问题的解得到原问题的解。就像打扫一个大房间，可以分成几个小区域分别打扫，最后整体就干净了。
分治算法的三个步骤：
1. 分解：将原问题分解成若干个规模较小的相同子问题。
2. 解决：递归地求解子问题。如果子问题足够小，直接求解。
3. 合并：将子问题的解合并成原问题的解。
18.1.2 分治程序范例：归并排序¶
归并排序是分治思想的经典应用。它的思想是：把数组分成两半，分别排序，然后合并两个有序数组。
#include <iostream>
using namespace std;
// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// 归并排序
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // 排序左半
mergeSort(arr, mid + 1, right); // 排序右半
merge(arr, left, mid, right); // 合并
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
cout << "排序结果：";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}
运行结果：3 9 10 27 38 43 82
归并排序体现了分治的精髓：先分后合。它的时间复杂度是 O(n log n)，很稳定。
18.1.3 分治的其他例子¶
快速排序（另一种分治）¶
快速排序也是分治，它选择一个基准值，把小于基准的放左边，大于基准的放右边，然后递归排序左右。
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
汉诺塔（分治思想）¶
汉诺塔问题也是分治：要把 n 个盘子从 A 移到 C，可以分解为：
1. 把上面 n-1 个盘子从 A 移到 B（借助 C）
2. 把最大的盘子从 A 移到 C
3. 把 n-1 个盘子从 B 移到 C（借助 A）
棋盘覆盖（趣味问题）¶
在一个 $2^k × 2^k$ 的棋盘中，有一个特殊方格，用 L 型骨牌覆盖所有方格（除了特殊格）。可以用分治：将棋盘分成四个小棋盘，特殊格在其中一个，其他三个小棋盘用 L 型骨牌覆盖，然后递归。
18.1.4 阶段性练习（分治）¶
- 练习1：用分治思想求一个数组的最大值和最小值（分成两半，分别求最大最小值，再合并）。
- 练习2：用归并排序对一组分数进行排序。
- 练习3：用分治实现二分查找（其实就是分治，但我们已经学过了）。
- 练习4：棋盘覆盖问题，尝试编写代码（选做）。
18.2 倍增算法¶
18.2.1 什么是倍增？¶
倍增就是“成倍增长”的意思。它的思想是：利用已知信息，通过每次跳 2^k 步来快速前进。比如你想知道从第 i 个位置出发，走 k 步后会到哪，如果一步步走很慢，但如果你事先知道从每个位置走 1 步、2 步、4 步……的位置，就能快速组合出 k 步。
倍增常用于：
- 快速幂
- 求最近公共祖先（LCA）
- 求区间最值（ST表）
- 跳跃游戏
18.2.2 倍增程序范例：快速幂¶
计算 a 的 b 次方，如果 b 很大，用循环乘 b 次很慢。快速幂用倍增思想：把 b 拆成二进制，每次平方底数。
#include <iostream>
using namespace std;
// 快速幂，计算 a^b
long long quickPow(long long a, int b) {
long long result = 1;
while (b > 0) {
if (b & 1) { // 如果 b 的二进制最低位是1
result *= a;
}
a *= a; // a 平方
b >>= 1; // b 右移一位
}
return result;
}
int main() {
int a, b;
cout << "请输入底数和指数：";
cin >> a >> b;
cout << a << "^" << b << " = " << quickPow(a, b) << endl;
return 0;
}
运行示例：输入 2 10，输出 1024。
原理：比如求 3^13，13 的二进制是 1101，即 3^13 = 3^8 × 3^4 × 3^1。我们通过不断平方得到 3^1, 3^2, 3^4, 3^8，然后根据需要乘起来。
18.2.3 ST表（区间最值查询）¶
ST表用于解决静态数组的区间最值查询（RMQ）问题。它用倍增预处理，查询时 O(1)。适合小学生理解的有趣应用：比如有一列数，快速问某个区间内的最大值。
思想：用 st[i][k] 表示从 i 开始，长度为 2^k 的区间内的最大值。那么：
- st[i][0] = arr[i]
- st[i][k] = max(st[i][k-1], st[i + (1 << (k-1))][k-1])（把区间分成两半，各长 2^(k-1)）
查询区间 [l, r] 时，计算长度 len = r-l+1，找到最大的 k 使得 2^k ≤ len，那么答案就是 max(st[l][k], st[r - (1<<k) + 1][k])（覆盖整个区间可能重叠，但不影响最值）。
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
const int LOG = 17; // 2^17 > 100000
int arr[MAXN];
int st[MAXN][LOG];
void buildST(int n) {
for (int i = 0; i < n; i++) st[i][0] = arr[i];
for (int k = 1; (1 << k) <= n; k++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}
}
}
int query(int l, int r) {
int k = log2(r - l + 1);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
int n, q;
cout << "请输入数组大小：";
cin >> n;
cout << "请输入数组元素：";
for (int i = 0; i < n; i++) cin >> arr[i];
buildST(n);
cout << "请输入查询次数：";
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
cout << "区间[" << l << "," << r << "]的最大值是：" << query(l, r) << endl;
}
return 0;
}
18.2.4 倍增求LCA（简单介绍）¶
LCA（最近公共祖先）是树上的问题。倍增预处理每个节点向上跳 2^k 步的祖先，查询时先把两个节点跳到同一深度，然后一起向上跳找公共祖先。这里只做概念介绍，不展开代码。
18.2.5 阶段性练习（倍增）¶
- 练习1：用快速幂计算 $5^13$ 和 $2^30$。
- 练习2：给定一个数组，用ST表求多个区间的最小值（只需把 max 改成 min）。
- 练习3：用倍增思想模拟“跳台阶”问题：有 n 级台阶，每次可以跳 1、2、3 级，问从第 0 级跳到第 n 级有多少种跳法？这不是倍增，但可以体会倍增的另一种应用：用矩阵快速幂优化递推。
- 练习4：查找数组中的某个数，用倍增思想做“指数搜索”（先以 $2^k$ 步长扩大范围，找到区间后二分）。
18.3 编程实例讲解¶
实例1：用分治求数组的最大子段和¶
题目：给定一个数组，求连续子数组的最大和（至少包含一个数）。例如 [-2,1,-3,4,-1,2,1,-5,4] 的最大子段和是 4-1+2+1 = 6。
分治思路：将数组分成两半，最大子段和要么在左半，要么在右半，要么跨越中点。跨越中点的可以从中点向两边扩展。
#include <iostream>
#include <algorithm>
using namespace std;
int maxCrossingSum(int arr[], int left, int mid, int right) {
int sum = 0;
int leftSum = -1e9;
for (int i = mid; i >= left; i--) {
sum += arr[i];
leftSum = max(leftSum, sum);
}
sum = 0;
int rightSum = -1e9;
for (int i = mid + 1; i <= right; i++) {
sum += arr[i];
rightSum = max(rightSum, sum);
}
return leftSum + rightSum;
}
int maxSubArraySum(int arr[], int left, int right) {
if (left == right) return arr[left];
int mid = left + (right - left) / 2;
int leftMax = maxSubArraySum(arr, left, mid);
int rightMax = maxSubArraySum(arr, mid + 1, right);
int crossMax = maxCrossingSum(arr, left, mid, right);
return max({leftMax, rightMax, crossMax});
}
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "最大子段和：" << maxSubArraySum(arr, 0, n - 1) << endl;
return 0;
}
实例2：用倍增求区间最大公约数（选做）¶
ST表也可以处理其他可重复贡献的问题，如 GCD（最大公约数）。因为 gcd 也满足结合律，且重叠不影响。
// 只需把 max 改成 __gcd 即可
实例3：用分治求平面最近点对（趣味介绍，不要求代码）¶
在平面上有 n 个点，求最近的两个点之间的距离。可以用分治：按 x 坐标排序，分成左右两半，分别求左右的最小距离 d，然后考虑跨左右且距离中线小于 d 的点，在 y 方向排序后比较。
18.4 第18章编程作业¶
作业1：归并排序实现¶
用归并排序对一组整数排序，并输出排序过程（每轮合并后的数组）。
作业2：快速幂取模¶
计算 a^b mod p，其中 a, b, p 都较大（用 long long）。要求用快速幂实现。
作业3：ST表求区间最小值¶
给定一个数组，多次询问区间最小值。用 ST 表预处理，回答查询。
作业4：分治求逆序对¶
在归并排序过程中，可以统计逆序对的数量。逆序对是指 i
作业5：倍增法求数组中的“下一个更大元素”（单调栈变体，但可以用倍增思想预处理每个元素跳 $2^k$ 步后的位置）¶
例如，给定数组 [2,1,5,6,2,3]，定义 next[i] 为从 i 开始往后第一个比 a[i] 大的元素的下标，若没有则为 -1。用倍增预处理，可以快速回答从 i 出发跳 k 步后的位置（但这里不是标准倍增，只是练习）。
作业6：棋盘覆盖问题（选做）¶
实现棋盘覆盖的代码，用分治算法，输出 L 型骨牌的放置。
恭喜你完成了第十八章的学习！分治和倍增是两种非常重要的算法思想，它们在很多高级算法中都有应用。分治让我们学会“拆解问题”，倍增让我们学会“快速跳跃”。加油！🚀