有人说分治还不会所以我就……

定义（3.1）

分治（英语：Divide and Conquer），字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

过程（3.2)

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

1.分解原问题为结构相同的子问题。 2.分解到某个容易求解的边界之后，进行递归求解。 3.将子问题的解合并成原问题的解。
分治法能解决的问题一般有如下特征：

1.该问题的规模缩小到一定的程度就可以容易地解决。 2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。 3.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

如果各子问题是不独立的，则分治法要重复地解公共的子问题，也就做了许多不必要的工作。此时虽然也可用分治法，但一般用 动态规划 较好。

以归并排序为例。假设实现归并排序的函数名为 merge_sort。明确该函数的职责，即 对传入的一个数组排序。这个问题显然可以分解。给一个数组排序等于给该数组的左右两半分别排序，然后合并成一个数组。

void merge_sort(一个数组) {
  if (可以很容易处理) return;
  merge_sort(左半个数组);
  merge_sort(右半个数组);
  merge(左半个数组, 右半个数组);
}

传给它半个数组，那么处理完后这半个数组就已经被排好了。注意到，merge_sort 与二叉树的后序遍历模板极其相似。因为分治算法的套路是 分解 -> 解决（触底）-> 合并（回溯），先左右分解，再处理合并，回溯就是在退栈，即相当于后序遍历。

merge函数的实现方式与两个有序链表的合并一致。

区别(3.3)

递归与枚举的区别(3.3.1)

递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题；而递归是把问题逐级分解，是纵向的拆分。

递归与分治的区别(3.3.2)

递归是一种编程技巧，一种解决问题的思维方式；分治算法很大程度上是基于递归的，解决更具体问题的算法思想。

例题详解（3.4）

#P1177. 【模板】快速/归并排序

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
void mergeSort(int l,int r){
	if(l==r) return ;
	int mid=(l+r)/2;
	mergeSort(l,mid);
	mergeSort(mid+1,r);
	int i=l;
	int j=mid+1;
	int index=l;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j]){
			b[index++]=a[i++];
		}else{
			b[index++]=a[j++];
		}
	}
	while(i<=mid){
		b[index++]=a[i++];
	}while(j<=r){
		b[index++]=a[j++];
	}
	for(int i=l;i<=r;i++){
		a[i]=b[i];
  }
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	mergeSort(1,n);
	for(int i=1;i<=n;i++) cout<<a[i]<<' ';
	return 0;
}

习题

#T1314. 【模板】合并序列 P1908逆序对