一 分治法概念
分治（divide-and-conquer），顾名思义分而治之。分治的核心是将原问题分解为同类型的规模更小的子问题，子问题往往可以求解或者求解比较简单，通过整合子问题的解得到原来问题的解。
分治的过程可以用如下图来表示：
由上述图示可发现整个分治过程是一颗树，而且子问题的处理过程是递归的处理（原问题与子问题是同类型）即为了解决一个给定的问题，算法一次或多次的调用其自身以解决紧密相关的若干子问题。
分治模式在每次递归时都有三个步骤：
1 分解原问题为若干子问题
2 解决这些子问题
3 整合子问题的解为原问题的解
二 分治法实例
2.1 归并排序
想要使用分治法实现归并排序，我们要先掌握合并两个有序数组，即将两个有序数组合并为一个。
现假设有两个有序数组L1和L2，长度分别为m和n，现将L1和L2合并为一个有序数组
解法：
1 开辟一个大小为m+n的数组L，并定义指针（索引）p = 0 指向L的起始位置
2 定义指针（索引）p1 = 0 指向L1的起始位置，定义指针（索引）p2 = 0 指向L2的起始位置
3 比较 L1[p1] 和 L2[p2] 的大小，若后者小 L[p++] = L2[p2++]，否则L[p++] =L1[p1++] 直到p1 == m
或 p2 ==n
4 将 L1 或者 L2 中剩余的元素拷贝到L
代码实现（c++）：
vector<int> merge(vector<int>& L1, vector<int>& L2)
{
int m = L1.size();
int n = L2.size();
vector<int>L(m + n);
int p = 0;
int p1 = 0, p2 = 0;
while (p1 < m && p2 < n)
{
if (L1[p1] <= L2[p2])
L[p++] = L1[p1++];
else
L[p++] = L2[p2++];
}
while(p1 < m) L[p++] = L1[p1++];
while(p2 < n) L[p++] = L2[p2++];
return L;
}
至此，你已经明白了合并两个有序数组，接下来我们将利用这个方法完成“赫赫有名”的归并排序。
不过在此之前，这里有两个题来检验你是否掌握这个方法：
归并排序完全遵守分治模式：
1 分解：将规模为n的待排序列分解为两个规模为n/2的两个待排子序列
2 解决：使用归并排序，对子序列完成排序
3 整合：将两个规模为n/2的有序序列合并为一个有序序列
归并排序难以理解的地方在于第2步，使用自身排序，但如果从递归的角度分析，当子序列规模为1时递归开始”回升“，此时规模为1的序列必然是有序的，将规模为1的子序列两两合并为规模为2的有序序列，接下来长度为2的子序列两两合并为长度为4的有序序列. . . . .直到将两个长度为n/2的子序列合并为长度为n的序列，就对待排序列完成了排序。
这里我们需要对merge函数做一些调整，此时不是合并两个独立的有序表，而是合并两个有序的区间中元素，并在合并后放回到原数组中两个连续区间中。
假设待排序列为nums ，merge调整后为：
void merge(vector<int>& nums, int l, int m, int r)
{
//分别是区间[l,m] 和 (m,r]
vector<int>f(r - l + 1);//分配辅助数组
int p = 0;
int p1 = l, p2 = m + 1;
while (p1 <= m && p2 <= r)
{
if (nums[p1] <= nums[p2])
f[p++] = nums[p1++];
else
f[p++] = nums[p2++];
}
while(p1 <= m)
f[p++] = nums[p1++];
while(p2 <= r)
f[p++] = nums[p2++];
//将元素按序放回到nums
p = 0;
p1 = l;
while (p < f.size()) nums[p1++] = f[p++];
}
调整完成，接下来将按照分治的模式写出归并排序，注意：递归的出口是规模为1
void mergesort(vector<int>& nums, int l, int r)//l r 分别表示待排序列的左右端点
{
if (l < r)
{
int m = (l + r) >> 1;//分解
mergesort(nums, l, m);//解决子问题[l,m]
mergesort(nums, m + 1, r);//解决子问题[m+1,r]
merge(nums, l, m, r);//整合子问题的解
}
}
测试结果如下：
归并排序到这里就结束了，至于它的复杂度，留待后续在推导。只需记住，归并排序是稳定排序，时间复杂度为O(nlogn)、空间复杂度为O(n)。
如果你看到这里，那么恭喜你！！！已经初步掌握了分治法，并且掌握了归并排序。
2.2 逆序对
如果在数组nums中，存在两个元素nums[i] 和nums[j] ，如果 i < j 并且nums[j] < nums[i] ，那么则称
(nums[i],nums[j])为一组逆序对。
我们的任务是给定数组nums,求出nums中的逆序对数
很容易想到，我们枚举所有的下标组合检查是否满足定义，如果满足则答案加1，枚举完成，即可得到答案
代码如下：
int getReverse(vector<int>& nums)
{
int n = nums.size();
int ans = 0;
for(int i = 0;i < n;i ++)
for (int j = i + 1; j < n; j++)
{
if (nums[j] < nums[i])
ans++;
}
return ans;
}
可能的下标组合个数为 （n-1）+（n-2）+ . . . . . + 1 = （n-1)*n/2
所以该算法的时间复杂度为O(n^2)。
如果我们用分治模式来分析这个问题，数组nums的长度为n，则将数组划分为[0,n/2]和（n/2,n）两个子问题
原问题的逆序对数 = 左边区间内的逆序对数 + 右边区间内的逆序对数 + 左边区间内的数与右边区间内的数形成的逆序对数
对于左边区间内的数与右边区间内的数形成的逆序对数如果左右区间内的数为有序序列，那么可以使用如下方法得到其逆序对数：
假设左区间位[l,m]，右区间位(m,r]
1 定义 p1 指向左区间起始位置， 定义 p2 指向右区间起始位置
2 如果 nums[p1] <= nums[p2]，因为nums[p2]后面的值都大于等于nums[p2],所以nums[p1]不会和nums[p2]及后面元素形成逆序对,所以p1++；如果nums[p1] > nums[p2]，那么nums[p2]将于nums[p1]及后面元素（截止到左区间结束）形成逆序对，即逆序对数位 m - p1 + 1,此时p2++
3 直到p1 == m 或者 p2 == r 此时不会再有逆序对
4 为了方便后续的计算，应将区间[l,r]内的元素变得有序
从上述过程不能看出，可以对merge函数进行调整，以达到目的
调整如下：
int merge(vector<int>& nums, int l, int m, int r)
{
//分别是区间[l,m] 和 (m,r]
vector<int>f(r - l + 1);//分配辅助数组
int ans = 0;//记录左边区间内的数与右边区间内的数形成的逆序对数
int p = 0;
int p1 = l, p2 = m + 1;
while (p1 <= m && p2 <= r)
{
if (nums[p1] <= nums[p2])
f[p++] = nums[p1++];
else
{
f[p++] = nums[p2++];
ans += (m - p1 + 1);
}
}
while(p1 <= m)
f[p++] = nums[p1++];
while(p2 <= r)
f[p++] = nums[p2++];
//将元素按序放回到nums
p = 0;
p1 = l;
while (p < f.size()) nums[p1++] = f[p++];
return ans;
}
采用分治模式为：
1 分解 统计区间[l,r]内的逆序对数分解为统计[l,(l+r)/2] 和((l+r)/2,r]内的逆序对数
2 解决 计算左右区间内的逆序对数
3 整合 左区间逆序对数 + 右区间逆序对数 + 左区间内数与右区间内数形成的逆序对数
当区间长度为1时，逆序对为0递归的出口
代码如下（c++)
int mergesort(vector<int>& nums, int l, int r)//l r 分别表示序列的左右端点
{
if (l < r)
{
int m = (l + r) >> 1;//分解
int left = mergesort(nums, l, m);//解决子问题[l,m]
int right = mergesort(nums, m + 1, r);//解决子问题[m+1,r]
int left_right = merge(nums, l, m, r);//
return left + right + left_right;
}
else
return 0;
}
到这里为止，“艺术已成”，如果仔细跟着思路走，我相信你应该对分治思想有了一定的了解。
这个算法的复杂度和归并排序一致，O(nlogn)，相对于枚举，有了很大的改善。
测试地址：
LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
2.3最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
同样的分治模式：
分解 为左右两区间
解决 求出左右区间内的最大子数组和 maxleft maxright
整合 最大子数组和 为maxleft maxright 与横跨两个区间的最大子数组和 三者中的最大者
问题的核心为求出横跨两个区间的最大子数组和
假设左右区间为[l,m]，[m+1,r]
该子数组必然在右区间起始于m+1,向r延伸
左区间始于m，向l延伸
左区间中起始于m的最大后缀和 + 右区间中起始于m+1的最大前缀和 就是所求的结果。
有了前面的经验，这里就不再附上代码，如有需要评论区留言！！！
谢谢你的观看，点赞 收藏 + 关注！！！！
标签：归并,p1,nums,int,-----,数组,区间,逆序 From： https://blog.csdn.net/2301_76686024/article/details/140631455