算法基础篇：（十五）基础算法之分治算法：从 “分而治之” 到实战攻坚，解锁高效解题新思路

前言

在算法的江湖里，有一类思想如同 “化骨绵掌”—— 它不直接与复杂问题硬刚，而是将其拆解成一个个小而可解的子问题，逐个击破后再整合结果。这就是我们今天的主角 ——分治算法。 分治，顾名思义 “分而治之”，是一种贯穿算法设计的核心思想，从基础的排序、查找，到高级的图像处理、大数据计算，都能看到它的身影。对于刚接触算法的开发者来说，掌握分治不仅能解决特定问题，更能培养 “拆解问题” 的思维能力。今天，我们就从分治的基本原理出发，结合逆序对、第 k 小数、最大子段和、地毯填补四大经典问题，手把手带你吃透分治算法，让你从 “看懂” 到 “会用”，再到 “灵活变通”。下面就让我们正式开始吧！

一、分治算法是什么？一篇文章讲透核心原理

在正式刷题之前，我们得先搞清楚：分治到底是 “何方神圣”？它的核心逻辑是什么？又有哪些关键步骤？

1.1 分治的核心思想：把大象装进冰箱需要几步？

小时候我们都听过 “把大象装进冰箱” 的笑话：第一步打开冰箱门，第二步把大象放进去，第三步关上冰箱门。虽然是笑话，但这恰好暗合了分治的思想 ——将一个庞大、复杂的问题，拆解成若干个规模较小、结构相同的子问题，分别解决子问题后，再将结果合并，得到原问题的解。

举个更具体的例子：如果让你计算 1+2+3+4+5+6+7+8，直接相加当然可以，但用分治的思路会更清晰：

• 分：把数组分成 [1,2,3,4] 和 [5,6,7,8] 两组；
• 治：分别计算两组的和，得到 10 和 36；
• 合：将两组的和相加，得到最终结果 46。

这就是分治的 “三步走” 策略，也是它的灵魂所在。

1.2 分治算法的三大特征

不是所有问题都能用分治解决，一个问题要适用分治，通常需要满足以下三个条件：

1. 问题可拆分：原问题可以分解为若干个规模较小、与原问题结构相同的子问题（比如计算数组和时，能拆分成两个子数组的和）；
2. 子问题可独立解决：子问题之间互不干扰，解决一个子问题不需要依赖另一个子问题的结果（比如两个子数组的和可以独立计算）；
3. 结果可合并：子问题的解可以通过某种方式合并，得到原问题的解（比如两个子数组的和相加，得到原数组的和）。

1.3 分治与递归的 “爱恨情仇”

很多人会把 “分治” 和 “递归” 搞混，其实它们是 “思想” 与 “实现方式” 的关系：

• 分治是算法思想：定义了 “分 - 治 - 合” 的解题框架；
• 递归是实现手段：分治的 “拆分” 和 “解决子问题” 步骤，通常用递归实现（因为子问题与原问题结构相同，适合自我调用）。

当然，分治也可以用迭代实现，但递归的代码更简洁、更贴合分治的逻辑。接下来我们讲的例题，都会用递归实现分治。

二、分治实战一：逆序对问题 —— 分治与排序的完美结合

逆序对是算法中的经典问题，也是分治思想的 “入门级实战题”。它不仅能帮我们理解分治的 “分 - 治 - 合” 流程，还能学会如何在分治中 “顺手” 优化其他操作（比如排序）。

题目链接如下：https://www.luogu.com.cn/problem/P1908

2.1 问题描述：什么是逆序对？

给定一个长度为 n 的正整数序列，逆序对指的是序列中满足 a[i] > a[j] 且 i < j 的有序对。例如序列 [5,4,2,6,3,1] 中，逆序对有 (5,4)、(5,2)、(5,3)、(5,1)、(4,2)、(4,3)、(4,1)、(2,1)、(6,3)、(6,1)、(3,1)，共 11 个。

我们的任务是，给定一个序列，计算其中逆序对的总数。

2.2 问题分析：暴力解法的困境与分治的突破

首先想到的是暴力解法：遍历所有可能的有序对 (i,j)，判断是否满足 a[i] > a[j] 且 i < j。但这种方法的时间复杂度是 O(n²)，对于 n=5×10⁵ 的数据（题目中的 100% 测试点），会直接超时 —— 这时候分治就该登场了。

用分治的思路分析逆序对问题：

1. 分：将序列从中间分成左半部分 [l, mid] 和右半部分 [mid+1, r]；
2. 治：分别计算左半部分、右半部分的逆序对数量（子问题，用递归解决）；
3. 合：计算 “左半部分的元素大于右半部分的元素” 的逆序对数量（这是分治的关键，也是最容易被忽略的部分）；
4. 总逆序对数量 = 左半部分逆序对数量 + 右半部分逆序对数量 + 跨左右的逆序对数量。

这里的关键是 “如何计算跨左右的逆序对数量”。如果左右两部分都是有序的，这个问题就会变得非常简单 —— 因为有序序列可以用 “双指针” 快速统计逆序对。

而 “让左右两部分有序” 这个操作，恰好可以通过归并排序实现。也就是说，我们可以在分治计算逆序对的同时，顺便完成归并排序 —— 这就是分治的 “一石二鸟” 之妙。

2.3 详细步骤：如何用分治 + 归并排序计算逆序对？

我们以序列 [5,4,2,6,3,1] 为例，一步步拆解分治过程：

步骤 1：拆分序列

将序列从中间 mid=2（下标从 0 开始）拆分为左半部分 [5,4,2] 和右半部分 [6,3,1]。

步骤 2：递归计算左右部分的逆序对

• 左半部分 [5,4,2] 递归拆分，最终计算出逆序对数量为 3（(5,4)、(5,2)、(4,2)）；
• 右半部分 [6,3,1] 递归拆分，最终计算出逆序对数量为 3（(6,3)、(6,1)、(3,1)）；
• 此时左右两部分经过归并排序后，分别变为 [2,4,5] 和 [1,3,6]。

步骤 3：计算跨左右的逆序对

用双指针 i（指向左半部分起点，即图中的cur1）和 j（指向右半部分起点，即图中的cur2），遍历两个有序序列：

• 初始 i=0，j=0，左半部分 [2,4,5]，右半部分 [1,3,6]；
• a[i]=2 > a[j]=1：说明左半部分中 i 及之后的所有元素（2,4,5）都大于 a[j]=1，共 3 个逆序对，j++；
• a[i]=2 <= a[j]=3：无逆序对，i++；
• a[i]=4 > a[j]=3：左半部分中 i 及之后的元素（4,5）都大于 3，共 2 个逆序对，j++；
• a[i]=4 <= a[j]=6：无逆序对，i++；
• a[i]=5 <= a[j]=6：无逆序对，i++；
• 遍历结束，跨左右的逆序对数量为 3+2=5。

步骤 4：合并结果

总逆序对数量 = 左半部分（3） + 右半部分（3） + 跨左右（5） = 11，与我们手动计算的结果一致。

2.4 代码实现：分治 + 归并排序

根据上述思路，我们可以写出逆序对问题的 C++ 代码：

#include <iostream>
using namespace std;

// 由于n可能达到5e5，需要用long long存储逆序对数量（避免溢出）
typedef long long LL;
const int N = 5e5 + 10;

int n;
int arr[N];    // 原数组
int tmp[N];    // 归并排序的临时数组

// 分治函数：计算[L, R]区间的逆序对数量，并对该区间进行归并排序
LL merge_sort(int L, int R) {
    // 递归终止条件：区间长度为1，无逆序对
    if (L >= R) {
        return 0;
    }

    // 1. 分：将区间拆分为左右两部分
    int mid = (L + R) >> 1;  // 等价于 (L+R)/2，位运算更快

    // 2. 治：递归计算左右两部分的逆序对数量
    LL res = 0;
    res += merge_sort(L, mid);    // 左半部分逆序对
    res += merge_sort(mid + 1, R); // 右半部分逆序对

    // 3. 合：计算跨左右的逆序对，并合并两个有序区间
    int i = L, j = mid + 1;  // 双指针：i指向左半部分，j指向右半部分
    int k = L;               // 临时数组的指针

    while (i <= mid && j <= R) {
        if (arr[i] <= arr[j]) {
            // 左半部分元素更小，无逆序对，直接放入临时数组
            tmp[k++] = arr[i++];
        } else {
            // 右半部分元素更小，左半部分i及之后的元素都与arr[j]构成逆序对
            res += (mid - i + 1);  // 统计逆序对数量
            tmp[k++] = arr[j++];
        }
    }

    // 处理剩余元素（左半部分或右半部分未遍历完的元素）
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= R) {
        tmp[k++] = arr[j++];
    }

    // 将临时数组的结果拷贝回原数组（完成归并排序）
    for (int t = L; t <= R; t++) {
        arr[t] = tmp[t];
    }

    return res;
}

int main() {
    // 输入数据
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 计算逆序对数量并输出
    cout << merge_sort(0, n - 1) << endl;

    return 0;
}

2.5 代码解析与测试

• 时间复杂度：O(n log n)。归并排序的时间复杂度是 O(n log n)，而分治过程中每个步骤的时间复杂度都与归并排序一致，因此整体时间复杂度为 O(n log n)，能轻松处理 n=5×10⁵ 的数据；
• 空间复杂度：O(n)。主要用于存储临时数组 tmp；
• 测试案例：输入：6 和 5 4 2 6 3 1输出：11（与手动计算结果一致）。

三、分治实战二：求第 k 小的数 —— 摆脱排序，高效查找

求第 k 小数是另一个经典的分治问题。如果用排序 + 直接取第 k 个元素的方法，时间复杂度是 O(n log n)，但用分治思想（快速选择算法），可以将时间复杂度优化到 O(n)（平均情况），效率更高。

题目链接如下：https://www.luogu.com.cn/problem/P1923

3.1 问题描述

给定 n 个正整数（n 为奇数），找出其中第 k 小的数（最小的数是第 0 小）。例如序列 [4,3,2,1,5] 中，第 1 小的数是 2。

要求：尽量不要使用 nth_element 等库函数，手动实现分治逻辑。

3.2 问题分析：排序的局限性与快速选择的优势

常规思路是 “排序后取第 k 个元素”，但排序会 “过度处理”—— 我们只需要第 k 小的数，不需要整个序列有序。分治的思路（快速选择算法）则可以 “按需处理”，只关注包含第 k 小数的子区间。

快速选择算法的核心思想源于快速排序，它的 “分 - 治 - 合” 流程如下：

1. 分：选择一个基准元素 p，将数组分为三部分：
   • 左部分：所有小于 p 的元素；
   • 中部分：所有等于 p 的元素；
   • 右部分：所有大于 p 的元素；
2. 治：根据左、中部分的长度，判断第 k 小数在哪个部分：
   • 如果 k < 左部分长度：第 k 小数在左部分，递归处理左部分；
   • 如果 k < 左部分长度 + 中部分长度：第 k 小数就是 p（因为中部分都是等于 p 的元素）；
   • 否则：第 k 小数在右部分，递归处理右部分（此时 k 需要减去左 + 中部分的长度）；
3. 合：由于只需要返回第 k 小数，不需要合并子问题的结果，直接返回找到的数即可。

这里的关键是 “选择基准元素”—— 如果每次都选到最差的基准（比如数组有序时选第一个元素），时间复杂度会退化为 O(n²)。为了避免这种情况，我们可以随机选择基准元素，这样平均时间复杂度能稳定在 O(n)。

3.3 详细步骤：以示例序列为例

我们以序列 [4,3,2,1,5]（求第 1 小的数）为例，拆解快速选择的过程：

步骤 1：随机选择基准元素

假设随机选择的基准元素 p=3（序列中的第二个元素）。

步骤 2：划分数组为三部分

• 左部分（小于 3）：[2,1]（长度 c1=2）；
• 中部分（等于 3）：[3]（长度 c2=1）；
• 右部分（大于 3）：[4,5]（长度 c3=2）。

步骤 3：判断第 k 小数的位置

我们要找的是第 k=1 小的数：

• 左部分长度 c1=2，k=1 < 2，说明第 k 小数在左部分；
• 递归处理左部分 [2,1]，此时 k 仍为 1。

步骤 4：递归处理左部分

对左部分 [2,1] 随机选择基准元素 p=2：

• 左部分（小于 2）：[1]（长度 c1=1）；
• 中部分（等于 2）：[2]（长度 c2=1）；
• 右部分（大于 2）：[]（长度 c3=0）。

判断第 k=1 小数的位置：

• 左部分长度 c1=1，k=1 == 1，说明第 k 小数在中部分（因为 k < c1 + c2 = 2）；
• 中部分的元素是 2，因此第 1 小的数是 2。

3.4 代码实现：快速选择算法

#include <iostream>
#include <ctime>  // 用于生成随机数种子
using namespace std;

const int N = 5e6 + 10;  // 题目中n最大接近5e6

int n, k;
int a[N];

// 生成[L, R]区间内的随机数（作为基准元素的下标）
int get_random(int L, int R) {
    // rand() % (R - L + 1) 生成0~(R-L)的随机数，加上L后得到[L, R]的随机数
    return rand() % (R - L + 1) + L;
}

// 分治函数：找到[L, R]区间内第k小的数（k从1开始，因为代码中k++了）
int quick_select(int L, int R, int k) {
    // 递归终止条件：区间长度为1，直接返回该元素
    if (L == R) {
        return a[L];
    }

    // 1. 分：随机选择基准元素，将数组分为三部分
    int pivot_idx = get_random(L, R);  // 随机选择基准元素的下标
    int pivot = a[pivot_idx];          // 基准元素的值

    // 双指针划分：x指向左部分的右边界，y指向右部分的左边界，i遍历数组
    int x = L - 1, y = R + 1;
    int i = L;
    while (i < y) {
        if (a[i] < pivot) {
            // 小于基准元素，放入左部分
            swap(a[++x], a[i++]);
        } else if (a[i] > pivot) {
            // 大于基准元素，放入右部分
            swap(a[--y], a[i]);
        } else {
            // 等于基准元素，留在中间部分
            i++;
        }
    }

    // 划分后：[L, x] < pivot，[x+1, y-1] == pivot，[y, R] > pivot
    int c1 = x - L + 1;  // 左部分长度
    int c2 = y - 1 - x;  // 中部分长度
    // int c3 = R - y + 1;  // 右部分长度（用不到）

    // 2. 治：判断第k小数在哪个部分
    if (k <= c1) {
        // 第k小数在左部分，递归处理左部分
        return quick_select(L, x, k);
    } else if (k <= c1 + c2) {
        // 第k小数在中部分，直接返回基准元素
        return pivot;
    } else {
        // 第k小数在右部分，递归处理右部分（k减去左+中部分的长度）
        return quick_select(y, R, k - c1 - c2);
    }
}

int main() {
    // 生成随机数种子（确保每次运行的随机数不同）
    srand((unsigned int)time(0));

    // 输入数据：n为数组长度，k为第k小（题目中k从0开始）
    scanf("%d%d", &n, &k);
    k++;  // 因为代码中k从1开始计算，所以加1

    // 读取数组（n最大5e6，用scanf比cin快）
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // 计算第k小的数并输出
    printf("%d\n", quick_select(0, n - 1, k));

    return 0;
}

3.5 代码解析与测试

• 时间复杂度：平均 O(n)，最坏 O(n²)（但随机选择基准元素后，最坏情况几乎不会出现）；
• 空间复杂度：O(log n)（递归栈的深度，平均情况下为 log n）；
• 测试案例：输入：5 1 和 4 3 2 1 5输出：2（与预期结果一致）。

注意：当 n 较大（如 5e6）时，用 cin 读取数据会很慢，因此代码中使用 scanf 提高输入效率。

四、分治实战三：最大子段和 —— 三次相遇，分治解法更深刻

最大子段和问题我们在贪心算法中已经见过，但分治解法能从另一个角度帮我们理解问题的本质。它不仅能解决问题，还能让我们学会如何处理 “跨区间” 的子问题。

题目链接如下：https://www.luogu.com.cn/problem/P1115

4.1 问题描述

给定一个长度为 n 的整数序列（序列中可能有负数），找出其中连续且非空的一段子序列，使得这段子序列的和最大。例如序列 [2, -4, 3, -1, 2, -4, 3] 中，最大子段和是 3 + (-1) + 2 = 4。

4.2 问题分析：分治如何处理 “连续子段”？

最大子段和的关键是 “连续”，因此分治的 “分 - 治 - 合” 需要考虑三种情况：

1. 最大子段完全在左半部分 [l, mid] 内；
2. 最大子段完全在右半部分 [mid+1, r] 内；
3. 最大子段跨越中间点 mid，左半部分的子段以 mid 结尾，右半部分的子段以 mid+1 开头。

分治的思路就是：

• 分：将序列从中间 mid 拆分为左右两部分；
• 治：递归计算左半部分和右半部分的最大子段和；
• 合：计算跨越中间点的最大子段和，然后取三者中的最大值作为原问题的解。

这里的核心是 “如何计算跨越中间点的最大子段和”—— 它可以拆分为两部分：

1. 从 mid 向左延伸，计算以 mid 为终点的最大子段和（左最大）；
2. 从 mid+1 向右延伸，计算以 mid+1 为起点的最大子段和（右最大）；
3. 跨越中间点的最大子段和 = 左最大 + 右最大。

4.3 详细步骤：以示例序列为例

我们以序列 [2, -4, 3, -1, 2, -4, 3]（n=7）为例，拆解分治过程：

步骤 1：拆分序列

mid = 3（下标从 0 开始），左半部分 [2, -4, 3, -1]，右半部分 [2, -4, 3]。

步骤 2：递归计算左右部分的最大子段和

• 左半部分 [2, -4, 3, -1] 递归计算，最大子段和为 3 + (-1) = 2；
• 右半部分 [2, -4, 3] 递归计算，最大子段和为 3。

步骤 3：计算跨越中间点的最大子段和

• 左最大（从 mid=3 向左延伸）：-1 → 3 + (-1) = 2 → -4 + 2 = -2 → 2 + (-2) = 0，取最大值 2；
• 右最大（从 mid+1=4 向右延伸）：2 → 2 + (-4) = -2 → -2 + 3 = 1，取最大值 2；
• 跨越中间点的最大子段和 = 2 + 2 = 4。

步骤 4：合并结果

原问题的最大子段和 = max (左部分 2, 右部分 3, 跨越中间点 4) = 4，与预期结果一致。

4.4 代码实现：分治求解最大子段和

#include <iostream>
#include <algorithm>  // 用于max函数
using namespace std;

const int N = 2e5 + 10;  // 题目中n最大2e5

int n;
int a[N];

// 分治函数：计算[L, R]区间的最大子段和
int divide_conquer(int L, int R) {
    // 递归终止条件：区间长度为1，最大子段和就是该元素本身
    if (L == R) {
        return a[L];
    }

    // 1. 分：拆分为左右两部分
    int mid = (L + R) >> 1;

    // 2. 治：递归计算左右两部分的最大子段和
    int left_max = divide_conquer(L, mid);    // 左部分最大子段和
    int right_max = divide_conquer(mid + 1, R); // 右部分最大子段和

    // 3. 合：计算跨越中间点的最大子段和
    // 3.1 计算左最大：从mid向左延伸的最大子段和
    int sum_left = a[mid];  // 初始值为mid位置的元素
    int max_left = sum_left;
    for (int i = mid - 1; i >= L; i--) {
        sum_left += a[i];
        max_left = max(max_left, sum_left);
    }

    // 3.2 计算右最大：从mid+1向右延伸的最大子段和
    int sum_right = a[mid + 1];  // 初始值为mid+1位置的元素
    int max_right = sum_right;
    for (int i = mid + 2; i <= R; i++) {
        sum_right += a[i];
        max_right = max(max_right, sum_right);
    }

    // 3.3 跨越中间点的最大子段和
    int cross_max = max_left + max_right;

    // 4. 返回三者中的最大值
    return max(max(left_max, right_max), cross_max);
}

int main() {
    // 输入数据
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 计算并输出最大子段和
    cout << divide_conquer(0, n - 1) << endl;

    return 0;
}

4.5 代码解析与测试

• 时间复杂度：O(n log n)。每次递归将问题拆分为两个子问题，每个子问题的规模是原问题的一半，合并步骤的时间复杂度是 O(n)，因此总时间复杂度为 O(n log n)；
• 空间复杂度：O(log n)（递归栈的深度）；
• 测试案例：输入：7 和 2 -4 3 -1 2 -4 3输出：4（与预期结果一致）。

对比贪心解法：贪心解法的时间复杂度是 O(n)，比分治更快，但分治解法更能体现 “拆解问题” 的思想，对于理解复杂问题（如二维最大子矩阵和）更有帮助。

五、分治实战四：地毯填补问题 —— 二维分治的经典之作

前面的例题都是一维问题，而地毯填补问题是二维分治的经典案例。它能帮我们理解如何将分治思想从 “线性” 扩展到 “平面”，是分治学习的 “进阶关卡”。

题目链接如下：https://www.luogu.com.cn/problem/P1228

5.1 问题描述

有一个 2^k × 2^k 的方形迷宫，其中有一个方格是公主的位置（不能用地毯覆盖）。我们需要用地毯将迷宫中除公主位置外的所有方格覆盖，地毯有四种形状（如下图所示），每种形状占 3 个方格，且只能覆盖相邻的方格（不能重叠、不能超出迷宫）。

我们的任务是，给定 k 和公主的坐标 (x, y)，输出每一步地毯的放置位置和形状。

5.2 问题分析：二维分治如何 “拆分” 迷宫？

迷宫是 2^k × 2^k 的正方形，恰好可以用分治拆分为四个 2^(k-1) × 2^(k-1) 的小正方形（左上、右上、左下、右下）。但此时有一个问题：四个小正方形中只有一个包含公主的位置（缺口），其他三个小正方形是 “完整的”，无法直接用分治处理（因为分治需要子问题结构相同）。

解决这个问题的关键是在迷宫中心放置一块地毯，人为地给三个完整的小正方形各制造一个 “缺口”。这样一来，四个小正方形都有一个缺口，结构相同，可以用递归处理。

具体步骤如下：

1. 分：将 2^k × 2^k 的迷宫从中心拆分为四个 2^(k-1) × 2^(k-1) 的小迷宫；
2. 补：根据公主所在的小迷宫，在中心放置一块地毯，给另外三个小迷宫各制造一个缺口；
3. 治：递归处理四个小迷宫（每个小迷宫都有一个缺口，与原问题结构相同）；
4. 合：无需合并结果，因为递归过程中已经输出了地毯的放置位置。

5.3 地毯形状与缺口位置的对应关系

地毯的四种形状对应四种缺口位置（公主所在的小迷宫）：

1. 公主在左上小迷宫：在中心放置形状 1 的地毯，给右上、左下、右下小迷宫制造缺口；
2. 公主在右上小迷宫：在中心放置形状 2 的地毯，给左上、左下、右下小迷宫制造缺口；
3. 公主在左下小迷宫：在中心放置形状 3 的地毯，给左上、右上、右下小迷宫制造缺口；
4. 公主在右下小迷宫：在中心放置形状 4 的地毯，给左上、右上、左下小迷宫制造缺口。

5.4 详细步骤：以 k=3，公主坐标 (3,3) 为例

迷宫大小为 8×8（2^3=8），公主在 (3,3)（左上小迷宫）：

步骤 1：拆分迷宫

将 8×8 迷宫拆分为四个 4×4 的小迷宫，中心位置为 (4,4)（2^(3-1)+1=5？不，k=3 时，2^(k-1)=4，中心坐标为 (4+1,4+1)=(5,5)）。

步骤 2：放置中心地毯

公主在左上小迷宫，因此在中心 (5,5) 放置形状 1 的地毯，给右上（缺口 (4,5)）、左下（缺口 (5,4)）、右下（缺口 (5,5)）小迷宫制造缺口。

步骤 3：递归处理四个小迷宫

• 左上小迷宫：公主位置 (3,3)，递归处理 4×4 迷宫；
• 右上小迷宫：缺口位置 (4,5)，递归处理 4×4 迷宫；
• 左下小迷宫：缺口位置 (5,4)，递归处理 4×4 迷宫；
• 右下小迷宫：缺口位置 (5,5)，递归处理 4×4 迷宫。

步骤 4：重复拆分与放置

每个小迷宫继续拆分为四个更小的迷宫，直到迷宫大小为 1×1（递归终止，无需放置地毯）。

5.5 代码实现：二维分治求解地毯填补问题

#include <iostream>
using namespace std;

// 分治函数：填补a行b列到x行y列的迷宫（大小为2^k × 2^k），公主在(x0,y0)
void dfs(int a, int b, int x0, int y0, int k) {
    // 递归终止条件：迷宫大小为1×1（k=0），无需放置地毯
    if (k < 1) {
        return;
    }

    // 计算迷宫的中心位置和小迷宫的大小
    int len = 1 << (k - 1);  // 小迷宫的边长：2^(k-1)
    int mid_x = a + len;      // 中心行坐标
    int mid_y = b + len;      // 中心列坐标

    // 1. 判断公主所在的小迷宫，放置中心地毯
    if (x0 < mid_x && y0 < mid_y) {
        // 公主在左上小迷宫：放置形状1的地毯，中心为(mid_x, mid_y)
        cout << mid_x << " " << mid_y << " 1" << endl;
        // 递归处理四个小迷宫
        dfs(a, b, x0, y0, k - 1);                  // 左上：公主在此
        dfs(a, mid_y, mid_x - 1, mid_y, k - 1);     // 右上：缺口(mid_x-1, mid_y)
        dfs(mid_x, b, mid_x, mid_y - 1, k - 1);     // 左下：缺口(mid_x, mid_y-1)
        dfs(mid_x, mid_y, mid_x, mid_y, k - 1);     // 右下：缺口(mid_x, mid_y)
    } else if (x0 < mid_x && y0 >= mid_y) {
        // 公主在右上小迷宫：放置形状2的地毯，中心为(mid_x, mid_y - 1)
        cout << mid_x << " " << mid_y - 1 << " 2" << endl;
        // 递归处理四个小迷宫
        dfs(a, b, mid_x - 1, mid_y - 1, k - 1);     // 左上：缺口(mid_x-1, mid_y-1)
        dfs(a, mid_y, x0, y0, k - 1);              // 右上：公主在此
        dfs(mid_x, b, mid_x, mid_y - 1, k - 1);     // 左下：缺口(mid_x, mid_y-1)
        dfs(mid_x, mid_y, mid_x, mid_y, k - 1);     // 右下：缺口(mid_x, mid_y)
    } else if (x0 >= mid_x && y0 < mid_y) {
        // 公主在左下小迷宫：放置形状3的地毯，中心为(mid_x - 1, mid_y)
        cout << mid_x - 1 << " " << mid_y << " 3" << endl;
        // 递归处理四个小迷宫
        dfs(a, b, mid_x - 1, mid_y - 1, k - 1);     // 左上：缺口(mid_x-1, mid_y-1)
        dfs(a, mid_y, mid_x - 1, mid_y, k - 1);     // 右上：缺口(mid_x-1, mid_y)
        dfs(mid_x, b, x0, y0, k - 1);              // 左下：公主在此
        dfs(mid_x, mid_y, mid_x, mid_y, k - 1);     // 右下：缺口(mid_x, mid_y)
    } else {
        // 公主在右下小迷宫：放置形状4的地毯，中心为(mid_x - 1, mid_y - 1)
        cout << mid_x - 1 << " " << mid_y - 1 << " 4" << endl;
        // 递归处理四个小迷宫
        dfs(a, b, mid_x - 1, mid_y - 1, k - 1);     // 左上：缺口(mid_x-1, mid_y-1)
        dfs(a, mid_y, mid_x - 1, mid_y, k - 1);     // 右上：缺口(mid_x-1, mid_y)
        dfs(mid_x, b, mid_x, mid_y - 1, k - 1);     // 左下：缺口(mid_x, mid_y-1)
        dfs(mid_x, mid_y, x0, y0, k - 1);           // 右下：公主在此
    }
}

int main() {
    int k, x, y;
    // 输入k和公主的坐标(x,y)
    cin >> k >> x >> y;
    // 调用分治函数：填补1行1列到(2^k)行(2^k)列的迷宫，公主在(x,y)
    dfs(1, 1, x, y, k);

    return 0;
}

5.6 代码解析与测试

• 时间复杂度：O(4^k)。每个迷宫拆分为 4 个小迷宫，共拆分 k 层，总共有 4^0 + 4^1 + ... + 4^k = (4^(k+1)-1)/3 个节点，每个节点对应一次地毯放置，因此时间复杂度为 O(4^k)；
• 空间复杂度：O(k)（递归栈的深度，等于拆分的层数 k）；
• 测试案例：输入：3 和 3 3输出：与题目中的示例输出一致（如 5 5 1、2 2 4 等）。

六、分治算法的常见误区与优化技巧

通过四个实战例题，我们已经掌握了分治的核心思想，但在实际使用中，还需要注意以下误区和优化技巧：

6.1 常见误区

1. 过度拆分：有些问题不需要拆到最小规模（如 1×1 或 1 个元素），可以在子问题足够小时用暴力解法（比如最大子段和中，当子问题规模小于 100 时，直接暴力计算，减少递归开销）；
2. 忽略子问题的独立性：如果子问题之间存在依赖（比如一个子问题的解需要另一个子问题的结果），则不能用分治（例如计算斐波那契数列，fib(n) = fib(n-1) + fib(n-2)，子问题依赖，分治会导致重复计算）；
3. 合并步骤效率低：分治的 “合” 步骤是关键，如果合并效率低（比如 O(n²)），会导致整体时间复杂度飙升（例如逆序对问题中，合并步骤如果用暴力统计，时间复杂度会退化为 O(n²)）。

6.2 优化技巧

1. 随机化选择基准：在快速选择、快速排序等分治算法中，随机选择基准元素可以避免最坏情况，稳定时间复杂度（如求第 k 小数问题）；
2. 尾递归优化：部分编译器支持尾递归优化（将递归转化为迭代），减少栈溢出风险（例如分治函数的最后一步是递归调用，可以改写为尾递归）；
3. 结合其他算法：分治可以与排序、双指针等算法结合，提高效率（如逆序对问题结合归并排序，最大子段和结合线性扫描）。

总结

分治算法不仅是一种解题技巧，更是一种 “拆解问题” 的思维方式。从一维的逆序对、最大子段和，到二维的地毯填补，分治算法展现了强大的灵活性和适用性。在未来的学习中，你还会遇到更多分治的应用（如 FFT 快速傅里叶变换、线段树分治等），但核心思想始终是 “分而治之”。 最后，送给大家一句话：分治的本质是 “化繁为简”，将看似不可能解决的大问题，拆解成一个个触手可及的小问题。 希望你能带着这份思维，在算法的路上走得更远！