LeetCode Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

思路：
range sum一般会转化为前缀和的问题prefix sum

解法（分治法）：

int countRangeSum(vector<int>& nums, int lower, int upper)
{
    //get the prefix sum
    vector<long long> prefix(nums.size() + 1, 0);
    for(int i = 1; i<=nums.size(); i++)
        prefix[i] = prefix[i-1] + nums[i-1];
    return countMergeSort(prefix, 0, nums.size(), lower, upper);
}
int countMergeSort(vector<long long>& prefix, int start, int end, int lower, int upper)
{
    if(start >= end) return 0;
    int mid = (start + end) >> 1;
    int count = countMergeSort(prefix, start, mid, lower, upper) + countMergeSort(prefix, mid+1, end, lower, upper);
    vector<long long> tmp(end-start+1);
    int lowerBound = mid+1, upperBound = mid+1, right = mid+1, tmpindex = 0;
    for(int left = start; left<=mid; left++)
    {
        while(lowerBound<=end && prefix[lowerBound] - prefix[left] < lower)
            lowerBound++;
        while(upperBound<=end && prefix[upperBound] - prefix[left] <= upper)
            upperBound++;
        count += upperBound - lowerBound;
        while(right<=end && prefix[right] < prefix[left])
            tmp[tmpindex++] = prefix[right++];
        tmp[tmpindex++] = prefix[left];
    }
    for(int i = 0; i<tmpindex; i++)
        prefix[start+i] = tmp[i];
    return count;
}

伴随着对prefix sum数组（不是原数组）的归并排序，我们在O(nlogn)时间找到了满足条件的前缀和之差的个数。