小和问题关于归并排序的思考

问题描述
在一个数组中， 每一个数左边比当前数小的数累加起来， 叫做这个数组的小和。 求一个数组 的小和。 例子： [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
解决思路
最简单的应该是一次遍历，但时间复杂度很高。转换一下思路可以变为右边比它大的数字有几个自身便加几次。所以数字本身便会和其右边数依次比较，此时时间复杂度能是o(n^2)，考虑归并排序的思想如果比较时其右边是有序的（相当于把之前的比较结果进行了存储），那么便可以减少比较的次数，时间复杂度降到o（n*logn）。
public static int sum(int []a,int l,int r) {
if(l==r) {
return 0;
}

小和问题关于归并排序的思考最先出现在Python成神之路。