归并分治的原理与补充说明
原理
- 思考一个大问题的答案是否等于小问题的答案之和：
- 将一个大问题分解为若干个小问题，分别求解这些小问题的答案。
- 如果左右两部分的答案是有序的，并且跨越左右产生的答案可以高效计算，那么整个问题可以通过归并的方式解决。
- 计算“跨越左右产生的答案”：
- 如果加上左、右各自有序这个设定，会获得计算的便利性。例如，在归并排序中，左右两部分已经是有序的，只需要通过合并操作即可得到最终的有序序列。
- 如果以上两点成立，那么这个问题很可能被归并分治解决：
- 因为总有一些很牛的“出题人”，他们会设计一些问题，使得归并分治成为一种高效的解决方案。
- 求解答案的过程中只需要加入归并排序的过程即可：
- 为了使左、右各自有序，从而获得计算的便利性，归并排序的核心思想就是先递归地将数组分成两部分，然后对这两部分分别进行排序，最后再将它们合并成一个有序的数组。
补充
- 一些用归并分治解决的问题，往往也可以用线段树、树状数组等数据结构解决：
- 时间复杂度也都是最优解。这些数据结构会在扩展课程阶段讲到。
- 本节课讨论的目标都是归并分治的常规题，难度不大：
- 归并分治不仅可以解决简单问题，还可以解决较难的问题。只要符合上面说的特征，比如多维空间里任何两点间的最短距离问题，这个内容会在《高级算法》课程阶段讲解。顶级公司考这个问题的也很少，因为很难。但是这个问题本身并不冷门，来自《算法导论》原题。
- 还有一个常考的算法：“整块分治”：
- 这个算法会在《必修》课程阶段讲到。
赞美：精妙又美丽的思想传统
- 归并分治的思想是一种非常优雅且高效的方法，它不仅适用于排序问题，还广泛应用于其他算法领域，如动态规划、区间查询等问题。通过将大问题分解为小问题，并利用小问题的有序性或独立性来高效求解，归并分治体现了算法设计中的智慧与美感。
归并分治-小和问题
问题描述
描述 数组小和的定义如下： \(\sum_{i=1}^{n} f_i\) 其中 $f_i$ 的定义是第 $i$ 个数的左侧小于等于 $s_i$ 的个数。
例如，数组 $s = [1, 3, 5, 2, 4, 6]$ ，在 $s[0]$ 的左边小于或等于 $s[0]$ 的数的和为 $0$ ； 在 $s[1]$ 的左边小于或等于 $s[1]$ 的数的和为 $1$ ；在 $s[2]$ 的左边小于或等于 $s[2]$ 的数的和为 $1+3=4$ ；在 $s[3]$ 的左边小于或等于 $s[3]$ 的数的和为 $1$ ； 在 $s[4]$ 的左边小于或等于 $s[4]$ 的数的和为 $1+3+2=6$ ；在 $s[5]$ 的左边小于或等于 $s[5]$ 的数的和为 $1+3+5+2+4=15$ 。所以 $s$ 的小和为 $0+1+4+1+6+15=27$ 给定一个数组 $s$ ，实现函数返回 $s$ 的小和
数据范围： \(0 < n \le 10^5\) \(|s_i| \le 100\)
输入描述： 第一行有一个整数N。表示数组长度 接下来一行N个整数表示数组内的数
输出描述： 一个整数表示答案
示例1 输入： 6 1 3 5 2 4 6
输出： 27
示例2 输入： 1 1
输出： 0
备注： \(1 \le N \le 10^5\) \(-100 \le arr_i \le 100\)
核心代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int merge(int l, int m, int r) {
// 统计部分
int ans = 0;
for (int i = l, j = m + 1, sum = 0; j <= r; j++) {
while (i <= m && arr[i] <= arr[j]) {
sum += arr[i++];
}
ans += sum;
}
// 正常归并...
return ans;
}
int smallSum(int l, int r){ // 求l~r的小和
if(l == r){
return 0;
}
int m = (l + r) / 2;
return smallSum(l, m) + smallSum(m + 1, r) + merge(l, m, r);
}
归并分治-翻转对（Reverse Pairs）
问题描述
给定一个数组 nums，如果存在 i < j 且 nums[i] > 2 * nums[j]，我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1:
1
2
输入: [1,3,2,3,1]
输出: 2
示例 2:
1
2
输入: [2,4,3,5,1]
输出: 3
注意
- 给定数组的长度不会超过 50000。
- 输入数组中的所有数字都在 32位整数 的表示范围内。
解法提示
可通过 归并排序、树状数组（Fenwick Tree） 或 线段树（Segment Tree） 实现高效求解。
核心代码:
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
int merge(int l, int m, int r){
if(l >= r){
return 0;
}
// 统计部分
int ans = 0;
for(int i = l, j = m + 1; i <= m; i++){
while(j <= r && nums[i] > 2 * nums[j]){
j++;
}
ans += j - m - 1;
}
// 正常归并...
return ans;
}
int counts(int l, int r){
if(l >= r){
return 0;
}
int m = l + (r - l) / 2;
return counts(l, m) + counts(m + 1, r) + merge(l, m, r);
}
int main(){
//...
}
