小和问题
在一个数组中， 每一个数左边比当前数小的数累加起来， 叫做这个数组的小和。 求一个数组
的小和。
例子：
[1,3,4,2,5]
1左边比1小的数， 没有；
3左边比3小的数， 1；
4左边比4小的数， 1、 3；
2左边比2小的数， 1；
5左边比5小的数， 1、 3、 4、 2；

所以小和为1+1+3+1+1+3+4+2=16

如果直接用两层for循环扫一遍，时间复杂度O(n*n)，这个题目可以利用归并排序把时间复杂度降到O(nlogn)

上代码

import java.io.BufferedInputStream;
import java.util.Scanner;

public class test {
    public static int[] help;

    public static int mergeSort(int[] a) {
        if (a == null || a.length < 2) {
            return 0;
        }
        help = new int[a.length];
        return sort(a, 0, a.length - 1);
    }

    public static int sort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return 0;
        }
        int mid = lo + ((hi - lo) >> 1);
        return sort(a, lo, mid) + sort(a, mid + 1, hi) + merge(a, lo, mid, hi); // 回到大区间的时候每部分都排好序了
    }

    public static int merge(int[] a, int lo, int mid, int hi) {
        int j = lo, k = mid + 1, res = 0;
        for (int i = lo; i <= hi; ++i) {
            help[i] = a[i];
        }
        for (int i = lo; i <= hi; ++i) {
            if (j > mid) {
                a[i] = help[k++];
            } else if (k > hi) {
                a[i] = help[j++];
            } else if (help[j] < help[k]) {
                res += (hi - k + 1) * help[j]; // k~hi之间的所有数都比help[j]大， res就是对help[j]来说前面小于它的数字之和
                a[i] = help[j++];
            } else {
                a[i] = help[k++];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt(); // 要排序的数量
        int[] a = new int[n]; // 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
        for (int i = 0; i < n; ++i) {
            a[i] = cin.nextInt();
        }
        cin.close();
        System.out.println(mergeSort(a)); // 在排好序的时候小数和已经求出来了
        /*if (n != 0) {
            System.out.print(a[0]);
        }
        for (int i = 1; i < n; ++i) {
            System.out.print(" " + a[i]);
        }*/
    }
}



========================================Talk is cheap, show me the code=======================================