在这一专栏，我将对经典算法及其例题进行整理和讲解，本篇文章的主题是：分治，我们将通过三道由浅入深的经典题目——“逆序对计数”、“子集和问题”与“平面最近点对”，一窥分治算法在序列处理、组合优化和几何问题三大领域的应用魅力。

🎯 本篇目标

  • 掌握分治思想的经典范式：归并应用、中途相遇和几何分治。
  • 理解“过程增强”、“解集合并”与“跨区域合并”的精髓，学会如何将 O(n²) 或 O(2^n) 的问题高效求解。
  • 领悟分治算法中“不变量”的设计与“空间换时间”的优美策略。

📌 食用指南

  • 题目已按从易到难的顺序排列，建议顺序阅读。目录支持锚点直达，每题均附 C++ 实现、图解与详细讲解。

🧭 分治思想速览

分治 (Divide and Conquer)，顾名思义，即“分而治之”。它是算法设计中的一种重要策略，其思想朴素而强大：一个难以直接解决的大问题，可以被分解成若干个规模更小、结构相同的子问题；独立解决这些子问题后在进行合并以得到原问题的解。

核心三步：

分解 (Divide)：将原问题划分为多个子问题。

解决 (Conquer)：递归地求解各个子问题。当子问题规模足够小（即到达递归出口）时，直接求解。

合并 (Combine)：将子问题的解合并成原问题的解。

🔖 题目索引

序号 题目名 难度 核心思想 平台 跳转
A 数组中的逆序对 困难 归并排序 分治 LeetCode 直达
B 世界冰球锦标赛 提高+/省选- 中途相遇 折半查找 洛谷 直达
C 平面最近点对 提高+/省选- 几何分治 区域划分 洛谷 直达

A. 数组中的逆序对

🧾 题目卡片

  • 平台：LeetCode | 原题链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
  • 标签：分治、归并排序
  • 核心考点：在经典分治算法（归并排序）的流程中附加计算任务。

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

  • 示例：输入 [7, 5, 6, 4]，输出 5。
  • 解释：逆序对有 (7,5), (7,6), (7,4), (5,4), (6,4)。

思路总览

O(n²) 的暴力解法会超时。

逆序对问题可以完美地嵌入到归并排序的分治过程中。

1. 分解 (Divide)

  • 将数组 record 从中间 mid 分成两个子数组 left_half 和 right_half。

2. 解决 (Conquer)

  • 递归地计算并排序 left_half，得到其内部的逆序对数 count_left。
  • 递归地计算并排序 right_half，得到其内部的逆序对数 count_right。

3. 合并 (Combine) - 在排序中计数

  • 目标：在将两个已排序的子数组 left_half 和 right_half 合并成一个大的有序数组的同时，计算出跨越这两个子数组的逆序对数量。
  • 计数原理：
    • 当我们从左子数组取出一个元素 L[i]，从右子数组取出一个元素 R[j] 进行比较时：
    • 如果 L[i] <= R[j]，则 L[i] 不可能与 R[j] 及之后的元素构成逆序对。
    • 如果 L[i] > R[j]，逆序对出现了！因为左子数组内部是有序的，所以 L[i] 以及它之后的所有元素都大于 R[j]。因此，R[j] 与左子数组中剩余的所有元素都构成了逆序对。
    • 我们将这个数量（即左子数组剩余元素个数）累加到总数中。

代码（C++）

点击展开   LeetCode C++ 完整实现代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int reversePairs(vector<int>& record) {
        if(record.empty()){
            return 0;
        }
        vector<int> temp(record.size());
        return mergeSort(record,temp,0,record.size()-1);
    }

    long long mergeSort(vector<int>& record,vector<int>& temp, int left,int right){
        if(left>=right){
            return 0;
        }

        int mid=left+(right-left)/2;

        long long count=mergeSort(record,temp,left,mid)+mergeSort(record,temp,mid+1,right);

        int i=left,j=mid+1,k=left;
        while(i<=mid&&j<=right){
            if(record[i]<=record[j]){
                temp[k++]=record[i++];
            }
            else{
                count+=(mid-i+1);
                temp[k++]=record[j++];
            }
        }
        while(i<=mid) temp[k++]=record[i++];
        while(j<=right) temp[k++]=record[j++];

        for(int l=left;l<=right;l++) {
            record[l]=temp[l];
        }

        return count;
    }
};

小结

“逆序对计数”展示了分治思想的第一种范式：过程增强。它并非为问题设计一个全新的分治流程，而是巧妙地利用了一个现有的、成熟的分治算法——归并排序。通过在 merge 这一核心步骤中，利用其“子数组已有序”的过程性不变量，顺便完成了计数任务。其精髓在于将问题求解与一个经典的分治过程融为一体。

B. 世界冰球锦标赛

🧾 题目卡片

  • 平台：洛谷 | 原题链接：https://www.luogu.com.cn/problem/P4799
  • 标签：分治、中途相遇、折半搜索
  • 核心考点：中途相遇算法的建模与实现。

题目描述

有 N 场比赛，每场比赛有一个花费 C_i。你有一个预算 M，问你有多少种选择比赛的方案，使得总花费不超过 M。 (1 ≤ N ≤ 40)

思路总览

这是一个典型的子集和计数问题。N 场比赛共有 2^N 种选择方案，当 N=40 时，2^40 的计算量是无法承受的。
这时候我们就要使用中途相遇 (Meet-in-the-Middle) 的思想。

1. 分解 (Divide)

  • 将 N 场比赛一分为二，N/2 约为 20，2^20 约为 10^6，这个规模的暴力搜索是可行的。

2. 解决 (Conquer)

  • 独立搜索：
    • 用 DFS 暴力枚举前半部分比赛的所有 2^(N/2) 种组合，将其花费和存入 vector sums1。
    • 同理，用 DFS 枚举后半部分，将花费和存入 sums2。

3. 合并 (Combine) - 高效配对

  • 目标：对于 sums1 中的每个和 c1，统计 sums2 中有多少个和 c2 满足 c1 + c2 ≤ M。
  • 优化：
    1. 排序：将 sums2 排序，为高效查找做准备。
    2. 二分查找：遍历 sums1 中的每个 c1，然后二分查找 sums2 中满足 c2 ≤ M - c1 的元素个数。可以直接使用C++ 的 upper_bound 函数来进行二分查找。

代码（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

// N: 比赛场数, M: 总预算
long long N, M;
// costs: 存储每场比赛的花费
vector<long long> costs;
// sums1, sums2: 分别存储前后两半部分所有子集的花费和
vector<long long> sums1, sums2;


void dfs(int l, int r, long long current_sum, vector<long long>& result) {
    // 剪枝：如果当前花费已经超预算，直接返回。
    if (current_sum > M) {
        return;
    }

    // 处理完指定范围内的所有比赛。
    if (l == r) {
        result.emplace_back(current_sum);
        return;
    }

    // 决策1：不选择第 l 场比赛。
    dfs(l + 1, r, current_sum, result);

    // 决策2：选择第 l 场比赛。
    dfs(l + 1, r, current_sum + costs[l], result);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    costs.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> costs[i];
    }

    int mid = N / 2;
    dfs(0, mid, 0, sums1);
    dfs(mid, N, 0, sums2);

    //对sums2进行排序，以便我们后面进行二分
    sort(sums2.begin(), sums2.end());

    long long total_count = 0;
    for (long long c1 : sums1) {
        long long remaining_budget = M - c1;
        auto it = upper_bound(sums2.begin(), sums2.end(), remaining_budget);
        total_count += (it - sums2.begin());
    }

    cout << total_count << endl;

    return 0;
}

小结

“中途相遇”是将指数级时间复杂度“开根号”。它体现了空间换时间的思想，通过将一个无法承受的 O(2^N) 搜索，分解为两次可接受的 O(2^(N/2)) 搜索，再通过 O(N * 2^(N/2)) 的高效合并完成求解。其精髓在于将搜索空间折半，在中间点汇合解集。

C. 平面最近点对

🧾 题目卡片

  • 平台：洛谷 | 原题链接：https://www.luogu.com.cn/problem/P1429
  • 标签：分治、计算几何
  • 核心考点：分治策略的设计、跨区域合并的剪枝优化、维持递归过程中的“不变量”。

题目描述

给定平面上 n 个点，找出其中的一对点的距离，使得在这 n 个点的所有点对中，该距离为所有点对中最小的。 (n ≤ 200000)

思路总览

O(n²) 的暴力解法会超时。

使用分治法可以做到O(n log n) 时间复杂度。

1. 分解 (Divide)

  • 预处理：将所有点按 x 坐标 排序，这是后续按位置划分的前提。
  • 分解：以中间点的 x 坐标 mid_x 为界，画一条垂直分割线，将点集分为左右两半。

2. 解决 (Conquer)

  • 递归：对左右两个子集分别递归调用，找出各自内部的最近距离 d_left 和 d_right。
  • 初步合并：暂定当前最小距离 d = min(d_left, d_right)。

3. 合并 (Combine)

  • 思考：真正的全局最近点对，除了完全在左边或完全在右边，还可能是一个点在左边，一个点在右边。我们称之为“跨区域点对”。
  • 剪枝：如果存在比 d 更短的跨界点对，那么这两个点在水平方向上离分割线的距离必然都小于 d。这让我们只需关注一个以分割线为中心、宽度为 2d 的“条带区域”。
  • 优化：将条带内的点按 y 坐标排序。可以证明，对于每个点，我们只需检查其后常数个点，即可找出所有可能的更优解（这是一个平面几何的结论，大家感兴趣的可以去自行了解）。
  • 算法不变量：为保证合并步骤的高效，我们需要确保每次递归返回的子集都是 y 轴有序的。这通过在递归返回后执行一次 O(n) 的归并 (merge) 操作来实现。

代码（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<limits>

using namespace std;

// 定义点结构体，使用 long long 存储坐标以防溢出
struct Point{
	long long x,y;
};

const int MAXN=200010; // 数组大小需满足题目最大 N
Point p[MAXN];
Point temp[MAXN]; // 归并操作的辅助数组

// 计算两点距离的平方，全程使用距离的平方以避免开方运算，只在最后输出时开方
long double distSq(const Point& a,const Point& b){
	return (long double)(a.x-b.x)*(a.x-b.x)+(long double)(a.y-b.y)*(a.y-b.y);
}

long double closestPairUtil(int left,int right){

	// 当区间内点数很少时（<=4个），无需继续分解，暴力求解
	if(right-left<=3){
		long double min_d_sq=numeric_limits<long double>::max();
        // 在暴力求解前，必须按 y 坐标排序，以保证上一层递归的归并操作能正确工作
		sort(p+left,p+right+1,[](const Point& a, const Point& b){
			return a.y<b.y;
		});

		for(int i=left;i<=right;i++){
			for(int j=i+1;j<=right;j++){
				min_d_sq=min(min_d_sq,distSq(p[i],p[j]));
			}
		}
		return min_d_sq;
	}
	
	int mid=left+(right-left)/2;
	long long mid_x=p[mid].x;
	
	// 递归求解左右两边的最近距离
	long double d_left_sq=closestPairUtil(left,mid);
	long double d_right_sq=closestPairUtil(mid+1,right);
	long double d_sq=min(d_left_sq,d_right_sq);
	
	// 归并操作：将左右两个已按y坐标排好序的子数组合并成一个大的y有序数组
	int i=left,j=mid+1,k=left;
	while(i<=mid&&j<=right){
		if(p[i].y<p[j].y) temp[k++]=p[i++];
		else temp[k++]=p[j++];
	}
	while(i<=mid) temp[k++]=p[i++];
	while(j<=right) temp[k++]=p[j++];
	for(int l=left;l<=right;l++) p[l]=temp[l];
	
	//筛选候选点：只收集中心条带区域内的点
	int strip_count=0;
	for(int l=left;l<=right;l++){
		if((long double)(p[l].x-mid_x)*(p[l].x-mid_x)<d_sq){
			temp[strip_count++]=p[l]; // 复用 temp 数组
		}
	}
	
	//检查候选点对：在 y 有序的候选点中进行最终检查
	for(int l=0;l<strip_count;l++){
        // 关键剪枝：内层循环最多执行常数次
		for(int m=l+1;m<strip_count&&(long double)(temp[m].y-temp[l].y)*(temp[m].y-temp[l].y)<d_sq;m++){
			d_sq=min(d_sq,distSq(temp[l],temp[m]));
		}
	}
	
	return d_sq;
}

int main(){

	int n;
	cin>>n;
	
	for(int i=0;i<n;i++){
		cin>>p[i].x>>p[i].y;
	}
	
	// 预处理：按 x 坐标排序
	sort(p,p+n,[](const Point& a,const Point& b){
		if(a.x!=b.x) return a.x<b.x;
		return a.y<b.y; 
	});
	
	long double result_sq=closestPairUtil(0,n-1);
	
	cout<<fixed<<std::setprecision(4)<<sqrt(result_sq)<<"\n";
	
	return 0;
}

小结

“平面最近点对”是几何分治的典范。它将一个看似需要全局比较的问题，通过递归地划分空间，将目光聚焦于关键的“边界区域”，并利用几何性质进行大胆而严谨的剪枝，最终将复杂度降至 O(n log n)。其精髓在于合并步骤中对跨区域解的高效处理。

📚 总结

  • 分治范式总结：
    1. 过程增强 (逆序对)：核心是在经典分治算法（如归并排序）的流程中，利用其过程特性（如子数组有序）来完成附加的计算任务。
    2. 规模折半 (中途相遇)：核心是将指数级的搜索空间折半，用空间换时间，然后在“中间点”对两边的解集进行合并。
    3. 区域划分 (最近点对)：核心是对问题所在的空间进行划分，并在合并时精巧地处理跨越边界的解。

💬 交流与反馈

  • 评论区：欢迎交流你的思路、代码优化建议或遇到的 bug。

🏁 感谢阅读 · 如果觉得有用，别忘了点赞、收藏与关注～