先来看一个题目

计算数组的小和

归并分治的原理

上面的示例中，左右部分都已经有序，这就使得计算左跨右的小和变得容易，只需定义左右两个指针，扫描左右部分
1）左指针元素小于等于右指针元素，将左指针元素加入sum中，左指针后移；

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int MAXN=100000;

    public static int[] arr=new int[MAXN];

    public static int[] help=new int[MAXN];

    public static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in=new StreamTokenizer(br);
        PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n=(int)in.nval;
        for(int i=0;i<n;i++){
            in.nextToken();
            arr[i]=(int)in.nval;
        }
        out.println(smallSum(0,n-1));
        out.flush();
        out.close();
    }
    // 当smallSum（l，r）调用完之后，arr[l...r]上是有序的
    // 返回值选择long类型，避免溢出
    public static long smallSum(int l,int r){
        if(l==r) return 0;
        int mid=(l+r)/2;
        return smallSum(l,mid)+smallSum(mid+1,r)+merge(l,mid,r);
    }
    public static long merge(int l,int m,int r){
        int sum=0;
        long ans=0;
        for(int j=m+1,i=l;j<=r;j++){
            while(i<=m && arr[i]<=arr[j]){
                sum+=arr[i++];
            }
            ans+=sum;
        }
        // 正常merge ，排序
        int i = l;
        int a = l;
        int b = m + 1;
        while (a <= m && b <= r) {
            help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= m) {
            help[i++] = arr[a++];
        }
        while (b <= r) {
            help[i++] = arr[b++];
        }
        for (i = l; i <= r; i++) {
            arr[i] = help[i];
        }
        return ans;
    }
}

翻转对

class Solution {
    public static int[] help=new int[50000];

    public int reversePairs(int[] nums) {
        return numPairs(nums,0,nums.length-1);
    }
    public static int numPairs(int[] nums,int l,int r){
        if(l==r) return 0;
        int mid=(l+r)/2;
        return numPairs(nums,l,mid)+numPairs(nums,mid+1,r)+merge(nums,l,mid,r);
    }
    public static int merge(int[] nums,int l,int m,int r){
        int ans=0;
        int sum=0;  //该元素的归并对数量
        for(int i=l,j=m+1;i<=m;i++){
            while(j<=r && (long)nums[i]>(long)2*nums[j]){
                sum++;
                j++;
            }
            ans+=sum;
        }
        //归并排序
        int i=l;
        int a=l,b=m+1;
        while(a<=m && b<=r){
            help[i++]=nums[a]<=nums[b]?nums[a++]:nums[b++];
        }
        while(a<=m) help[i++]=nums[a++];
        while(b<=r) help[i++]=nums[b++];
        for(int k=l;k<=r;k++) nums[k]=help[k];
        return ans;
    }
}