分治算法

概念讲解

什么是分治？

分治是将问题分解为子问题，递归解决子问题，再合并结果的算法思想。

步骤

1. 分： 分解问题
2. 治： 解决子问题
3. 合： 合并结果

经典应用

1. 归并排序求逆序对

123456789101112131415161718192021int mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    int cnt = mergeSort(a, l, mid) + mergeSort(a, mid+1, r);
    
    vector<int> temp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp.push_back(a[i++]);
        } else {
            temp.push_back(a[j++]);
            cnt += mid - i + 1;  // 统计逆序对
        }
    }
    while (i <= mid) temp.push_back(a[i++]);
    while (j <= r) temp.push_back(a[j++]);
    
    for (int i = l; i <= r; i++) a[i] = temp[i-l];
    return cnt;
}

时间复杂度：$O(n \log n)$

2. 快速幂

123456long long quickPower(long long a, long long n) {
    if (n == 0) return 1;
    long long half = quickPower(a, n / 2);
    if (n % 2 == 0) return half * half;
    return half * half * a;
}

考点分析

初赛考查方式

1. 程序阅读： 分治程序
2. 编程题： 分治应用

常见考点

• 归并排序
• 逆序对
• 快速幂

例题精讲

例题 1：逆序对

题目： 求数组的逆序对数量。

解答：

使用归并排序，在合并时统计逆序对。

练习题

1. 分治的三个步骤是什么？

2. 归并排序的时间复杂度是多少？

3. 如何用分治求逆序对？

123456if (a[i] <= a[j]) {
    temp.push_back(a[i++]);
} else {
    temp.push_back(a[j++]);
    cnt += mid - i + 1;  // 统计逆序对
}

易错点

⚠️ 注意：

1. 分治要保证子问题独立
2. 合并时统计逆序对
3. 时间复杂度通常是 O(n log n)
4. 注意递归终止条件