分治算法（Divide and Conquer）是一种重要的算法设计策略，其核心思想是将一个复杂问题分解为多个相似的子问题，递归解决这些子问题，然后合并子问题的解得到原问题的解。下面从基础概念到高级应用，为你提供一份全面的C++分治算法教程。

1. 分治算法基本原理

分治算法遵循三个基本步骤：

1. 分解（Divide）：将原问题分解为多个规模更小、结构相似的子问题。
2. 解决（Conquer）：递归求解每个子问题。若子问题足够小，则直接求解。
3. 合并（Combine）：将子问题的解合并为原问题的解。

2. 经典案例：归并排序（Merge Sort）

归并排序是分治算法的典型应用，其步骤如下：

• 分解：将数组分成两个子数组。
• 解决：递归排序两个子数组。
• 合并：合并两个已排序的子数组。

#include <iostream>
#include <vector>
using namespace std;

// 合并两个已排序的子数组
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// 归并排序主函数
void mergeSort(vector<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() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    int n = arr.size();

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

复杂度分析：

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$（主要用于合并过程的临时数组）

3. 快速排序（Quick Sort）

快速排序也是分治算法的经典应用，步骤如下：

• 分解：选择基准值（pivot），将数组分为两部分，左半部分小于等于基准值，右半部分大于基准值。
• 解决：递归排序左右两部分。
• 合并：无需合并，因为分解时已保证左右两部分的顺序关系。

#include <iostream>
#include <vector>
using namespace std;

// 分区函数，选择最后一个元素作为基准值
int partition(vector<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(vector<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);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

复杂度分析：

• 平均时间复杂度：$O(n \log n)$
• 最坏时间复杂度：$O(n^2)$（可通过随机选择基准值避免）
• 空间复杂度：$O(\log n)$（递归栈空间）

4. 分治策略优化技巧

4.1 减少递归次数

某些问题可通过合并子问题的解减少递归调用。例如，Karatsuba乘法通过优化多项式乘法，将递归次数从4次减少到3次，时间复杂度从$O(n^2)$降至$O(n^{1.585})$。

4.2 预处理与后处理

在分解前预处理数据，或在合并后处理结果，可提高效率。例如，在并行计算中，预处理数据可减少通信开销。

5. 高级应用：最近点对问题

问题描述：在平面上给定n个点，找出距离最近的一对点。

分治解法：

1. 分解：按x坐标排序后，将点集分为左右两部分。
2. 解决：递归求解左右两部分的最近点对。
3. 合并：检查跨越分割线的点对是否存在更近的距离。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <float.h>
using namespace std;

struct Point {
    double x, y;
};

// 比较函数：按x坐标排序
bool compareX(const Point& a, const Point& b) {
    return a.x < b.x;
}

// 比较函数：按y坐标排序
bool compareY(const Point& a, const Point& b) {
    return a.y < b.y;
}

// 计算两点间距离
double distance(const Point& a, const Point& b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

// 暴力求解小规模问题
double bruteForce(const vector<Point>& points, int left, int right) {
    double minDist = DBL_MAX;
    for (int i = left; i < right; i++) {
        for (int j = i + 1; j < right; j++) {
            minDist = min(minDist, distance(points[i], points[j]));
        }
    }
    return minDist;
}

// 分治求解最近点对
double closestUtil(vector<Point>& points, int left, int right) {
    if (right - left <= 3) return bruteForce(points, left, right);

    int mid = left + (right - left) / 2;
    Point midPoint = points[mid];

    double dLeft = closestUtil(points, left, mid);
    double dRight = closestUtil(points, mid, right);
    double d = min(dLeft, dRight);

    // 构建中间带
    vector<Point> strip;
    for (int i = left; i < right; i++) {
        if (abs(points[i].x - midPoint.x) < d) {
            strip.push_back(points[i]);
        }
    }

    // 按y坐标排序
    sort(strip.begin(), strip.end(), compareY);

    // 检查中间带内的点对
    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d; j++) {
            d = min(d, distance(strip[i], strip[j]));
        }
    }

    return d;
}

double closestPair(vector<Point>& points) {
    sort(points.begin(), points.end(), compareX);
    return closestUtil(points, 0, points.size());
}

int main() {
    vector<Point> points = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
    double minDist = closestPair(points);
    cout << "The closest distance is: " << minDist << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n \log n)$（排序和递归合并的总复杂度）

6. 分治与动态规划的对比

分治算法	动态规划
子问题相互独立	子问题重叠
递归求解	迭代求解（通常）
重点在分解与合并	重点在状态转移方程
例如：归并排序、快速排序	例如：斐波那契数列、背包问题

7. 练习题目推荐

1. LeetCode 241. 为运算表达式设计优先级
   给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。

2. LeetCode 53. 最大子数组和
   给定一个整数数组，找到一个具有最大和的连续子数组，返回其最大和。

3. LeetCode 169. 多数元素
   给定一个大小为n的数组，找到其中的多数元素（出现次数大于 ⌊n/2⌋ 的元素）。

总结

分治算法通过分解、解决、合并三个步骤，将复杂问题转化为简单子问题，是设计高效算法的重要策略。掌握分治思想需要多练习经典案例，并理解递归与合并的核心逻辑。