[LeetCode] Count of Range Sum

参考：https://leetcode.com/discuss/79083/share-my-solution
照着人家的写了一个，原文解释的很详细了，稍微改了改。

public class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) return 0;
        long[] prefixSum = new long[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) prefixSum[i] = prefixSum[i-1] + nums[i];
        return mergeCount(prefixSum, 0, nums.length - 1, lower, upper);
    }

    private int mergeCount(long[] prefixSum, int start, int end, int lower, int upper) {
        if (start == end) {
            if (prefixSum[start] >= lower && prefixSum[start] <= upper) return 1;
            else return 0;
        }
        int mid = (start + end) / 2;
        int count = mergeCount(prefixSum, start, mid, lower, upper);
        count += mergeCount(prefixSum, mid + 1, end, lower, upper);
        long[] left = new long[mid - start + 1];
        long[] right = new long[end - mid];
        for (int i = 0; i < mid - start + 1; i++) left[i] = prefixSum[start + i];
        for (int i = 0; i < end - mid; i++) right[i] = prefixSum[mid + 1 + i];
        for (int leftIndex = 0, lowerBound = 0, upperBound = 0, rightIndex = 0, index = start; leftIndex < mid - start + 1; leftIndex++) {
            while (lowerBound < end - mid && right[lowerBound] - left[leftIndex] < lower) lowerBound++;
            while (upperBound < end - mid && right[upperBound] - left[leftIndex] <= upper) upperBound++;
            count += upperBound - lowerBound;
            while (rightIndex < end - mid && right[rightIndex] < left[leftIndex]) prefixSum[index++] = right[rightIndex++];
            prefixSum[index++] = left[leftIndex];
        }
        return count;
    }
}