Count of Range Sum

题目来源
给一个数组，求在某个范围内的子串和个数。
这道题搞了半天，理解了半天，写了半天，感觉自己弱爆了。
主要在于利用和数组，利用归并排序，分成两堆的时候，前后是有序的，就是说右堆的元素在左堆的元素和索引的后边，所以可以直接两个和相减表示原数组的某个子串和。
然后归并排序的过程也很巧妙，利用了一个cache来存储排好序的数组。
左堆和右堆元素比较，因为左右堆都是各自排好序的，所以其实本质上就是双指针向后移动。

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int n = nums.size();
        if (n == 0)
            return 0;
        vector<long long> sums(n+1, 0);
        for (int i=0; i<n; i++)
            sums[i+1] = sums[i] + nums[i];
        return mergeSortWhileCount(sums, 0, n+1, lower, upper);
    }
    
    int mergeSortWhileCount(vector<long long>& sums, int start, int end, int lower, int upper)
    {
        if (end - start <= 1)
            return 0;
        int mid = (start + end) / 2;
        int cnt = mergeSortWhileCount(sums, start, mid, lower, upper)
        + mergeSortWhileCount(sums, mid, end, lower, upper);
        int j = mid, k = mid, t = mid, len = 0;
        vector<long long> cache(end-start, 0);
        for (int i=start, s=0; i<mid; i++, s++) {
            while (j < end && sums[j] - sums[i] < lower) j++;
            while (k < end && sums[k] - sums[i] <= upper) k++;
            while (t < end && sums[t] < sums[i]) cache[s++] = sums[t++];
            cache[s] = sums[i];
            len = s;
            cnt += k - j;
        }
        for (int i=0; i<=len; i++)
            sums[start+i] = cache[i];
        return cnt;
    }
};