给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-of-range-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public static int countRangeSum(int[] nums, int lower, int upper) {
        long[] sum = new long[nums.length + 1];
        for (int i = 1; i <= nums.length; ++i) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        return solveWhileMergeSort(sum, 0, sum.length - 1, lower, upper);
    }

    private static int solveWhileMergeSort(long[] sum, int L, int R, int lower, int upper) {
        if (L == R) {
            return 0;
        }
        int mid = (L + R) >> 1;
        int ret = solveWhileMergeSort(sum, L, mid, lower, upper) + solveWhileMergeSort(sum, mid + 1, R, lower, upper);

        int left = mid + 1, right = mid + 1;
        int i = L;
        while (i <= mid) {
            while (left <= R && sum[left] - sum[i] < lower) {
                left++;
            }
            while (right <= R && sum[right] - sum[i] <= upper) {
                right++;
            }
            i++;
            ret += (right - left);
        }

        int p1 = L, p2 = mid + 1;
        int index = 0;
        long[] helper = new long[R - L + 1];
        while (p1 <= mid && p2 <= R) {
            if (sum[p1] <= sum[p2]) {
                helper[index++] = sum[p1++];
            } else {
                helper[index++] = sum[p2++];
            }
        }

        while (p1 <= mid) {
            helper[index++] = sum[p1++];
        }

        while (p2 <= R) {
            helper[index++] = sum[p2++];
        }

        System.arraycopy(helper, 0, sum, L, helper.length);

        return ret;
    }

    public static void main(String[] args) {
        int[] nums = {0};
        int lower = 0;
        int upper = 0;
        System.out.println(countRangeSum(nums, lower, upper));
    }
}