小和问题

小和问题–逆向思维-使用归并思想

public class LittleAdd {
    int ans = 0;
    public int littltAdd(int[] nums){
        process(nums, 0, nums.length-1);
        return ans;
    }

    public void process(int[] arr, int l, int r){
        if (l==r) return;
        int mid = l+((r-l)>>1);
        process(arr, l, mid);
        process(arr, mid+1, r);
        megerSort(arr, l, mid, r);
    }

    public void megerSort(int[] arr, int l, int m, int r){
        int[] help = new int[r-l+1];
        int i = 0;
        int p1 = l;
        int p2 = m+1;
        while (p1 <= m && p2 <= r){
            if (arr[p1] < arr[p2]){
                help[i++] = arr[p1];
                ans += (r-p2+1) * arr[p1];
            }else{
                help[i++] = arr[p2];
            }
        }
    }
}