归并排序是计算机之父"冯·诺依曼"发明的,但这其中隐藏了一种归并分治的思想。这种思想在一些题目中会帮助我们解决很多问题。

原理

1. 对于一个大问题的答案，如果等于左边子问题的答案 + 右边子问题的答案 + 跨越左右问题的答案。
2. 在计算跨越左右问题的答案时，左右两边是有序的是否会对我们计算答案产生便利。
3. 如果以上两点都成立，那么很可能是用归并分治的思想来解决问题。

一些用归并分治解决的问题大部分也可以用线段树和树状数组来解决。时间复杂度也是最优的。

翻转对

力扣题目链接

解题思路

1. 我们先分析求一个区间的翻转对的个数，是不是等于求左边区间翻转对的个数加右边区间翻转对的个数，加跨越左右区间翻转对的个数
2. 很明显，一个区间的翻转对的个数等于左边区间翻转对的个数加右边区间翻转对的个数，加跨越左右区间翻转对的个数。
3. 用分治法求子数组的最大累加和一样，最大累加和就是左边连续子数组的最大累加和，和右边连续子数组的最大累加和，但这还没有包括全部情况，也就是还有跨越区间的累加和。
4. 对于这道题，因为i < j，所以翻转对的个数不就是左边区间翻转对的个数和跨越左右的区间的翻转对的个数吗，那么左边就考虑完了，就剩右边了，因为 i < j，那么左边的就肯定不满足翻转对。所以就只要算右边区间翻转对的个数。
5. 然后再思考左右俩边区间有序对我们计算翻转对的个数会不会带来方便。

代码实现

//归并分治
int help[50000];//辅助数组
int merge(int* a, int l, int m, int r) {
    int ans = 0;
    int len = 0;

    for (int i = l, j = m + 1; i <= m ; i++) {//统计翻转对的个数,j的含义是a[j] * 2 >= a[i]的第一个位置
        while(j <= r && (long long)a[i] > (long long)a[j] * 2) {//如果a[j] * 2 >= a[i]或者越界了，就跳出不然就找下一个 
            j++;//跳下一个
        }
        ans += j - (m + 1);//右边的起始位置是m + 1，而j是a[j] * 2 >= a[i]的位置，因此它前面数都是翻转对，因为是有序的
    }

    //正常合并两个有序表
    int i = l;
    int j = m + 1;

    while(i <= m && j <= r) {
        if (a[i] <= a[j]) {
            help[len++] = a[i++];
        }
        else {
            help[len++] = a[j++];
        }
    }

    while(i <= m) {
        help[len++] = a[i++];
    }

    while(j <= r) {
        help[len++] = a[j++];
    }

    for (int k = 0; k < len; k++) {
        a[l + k] = help[k];
    }

    return ans;
}
//求[l, r]区间上的翻转对，并让[l, r]位置有序
int f(int* a, int l, int r) {
    if (l >= r) {
        return 0;
    }

    int mid = (l + r) / 2;

    return f(a, l, mid) + f(a, mid + 1, r) + merge(a, l, mid, r);//左子问题的答案加上右子问题的答案加上跨越左右问题的答案
}
int reversePairs(int* nums, int numsSize) {
    return f(nums, 0, numsSize - 1);
}

总结

归并分治也是一种分治法，所以分治法是一种重要的思想，归并分治能够使用题目大部分都符合前面两个特征，那么就可以用归并分治。