• 算法
    • 归并排序
    • 1.计算前缀和sums[i]表示[0, i)的元素之和
    • 2.对前缀和进行归并排序，在归并的过程中对已有序的数组统计左半部分和右半部分组成的下标对满足sum[j]-sum[i]的个数
      • 有序数组sum[left, mid]和sum[mid+1, right]
      • 左下标对在外层循环[left, mid]，右下标对在内层l和r双指针做循环，找到可以和左下标对匹配的范围，加到最终结果中 
public int countRangeSum(int[] nums, int lower, int upper) {
    long[] sums = new long[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        sums[i + 1] = sums[i] + nums[i];
    }
    return countRangeSumRecursive(sums, lower, upper, 0, sums.length - 1);
}

private int countRangeSumRecursive(long[] sum, int lower, int upper, int left, int right) {
    if (left == right) {
        return 0;
    } else {
        int mid = (left + right) >> 1;
        int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
        int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
        int result = n1 + n2;

        // 首先统计下标对的数量
        int i = left;
        int l = mid + 1;
        int r = mid + 1;
        while (i <= mid) {
            while (l <= right && sum[l] - sum[i] < lower) {
                l++;
            }
            while (r <= right && sum[r] - sum[i] <= upper) {
                r++;
            }
            result += r - l;
            i++;
        }

        // 随后合并两个排序数组
        // Arrays.sort(sum, left, right+1);
        int[] sorted = new int[right - left + 1];
        int p1 = left, p2 = mid + 1;
        int p = 0;
        while (p1 <= mid || p2 <= right) {
            if (p1 > mid) {
                sorted[p++] = (int) sum[p2++];
            } else if (p2 > right) {
                sorted[p++] = (int) sum[p1++];
            } else {
                if (sum[p1] < sum[p2]) {
                    sorted[p++] = (int) sum[p1++];
                } else {
                    sorted[p++] = (int) sum[p2++];
                }
            }
        }
        for (int j = 0; j < sorted.length; j++) {
            sum[left + j] = sorted[j];
        }
        return result;
    }
}