题解 | #数组单调和(小和问题)#

问题转化：求单调和（小和）就是统计该元素前有多少小于等于该数的元素之和。问题和归并两个有序数组求小于等于该数的元素之和一样。所以现在的问题变为统计子问题中单调和。

        // 当出现nums[i]<=nums[j]时，统计所有前半段区间内比nums[j]小的数
        // 当前一个数组元素小于或等于后一个数组元素时，累加小和
        // s[i] <= s[j] -> s[i] <= s[j]...s[right]
		while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]){
                //当出现nums[i]<=nums[j]时，统计所有前半段区间内比nums[j]小的数
                // 当前一个数组元素小于或等于后一个数组元素时，累加小和
                // s[i] <= s[j] -> s[i] <= s[j]...s[right]
                res += a[p1] * (right - p2 + 1);
                temp[k++] = a[p1++];               
            } else{
                temp[k++] = a[p2++];
            }               
        }