题目描述

这道题给了我们一个数组，又给了我们一个下限和一个上限，让我们求有多少个不同的区间使得每个区间的和在给定的上下限之间

样例

 nums = [-2, 5, -1]
 下限 = -2, 上限 = 2
 返回3

算法

(分治) $O(n*log(n))$

先求前缀和。
对于区间[i,j]（左闭右闭） 其中的区间和可以表示为 Sums[j] - Sums[i-1]

然后对于前缀和进行分治。
之所以对前缀和进行归并，因为前缀和可以用于计算区间和。
分治一般思想是先分后和。
分的时候分一半，为了均匀（提高效率） 分为左边和右边。

例如一段区间为[l,r) 分为 [l,mid) [mid,r)
最后的结果由两部分构成，一部分是划分的两个子集内部的区间和。另一个是两个子集相互作用涉及到的区间和。
第一部分：
按照递归的定义可以直接求得。

第二部分
接下来求组间距离,对于任意的一个区间都可以表示为Sums[i]-Sums[j], 并且 i属于右区间，j属于左区间。
要求 lower<=Sums[i] - Sums[j]<=upper
等价于 lower+Sums[j] <= Sums[i] <= Sums[j] + upper
那么我们只需要枚举左侧的每一个前缀和，再加上上下界，就可以确定对应的右前缀和对应的上下界。
求出右前缀和对应的上下界以后，我们就可以得到当前的左前缀和对应有多少个右前缀和。
可以找出在右侧前缀和中的下界的下标和上界的下标，用上界的下标减去下界的下标就可以算出当前的左前缀对应的右前缀有多少个了。
这里需要注意，这时候右侧不一定是按照原来的顺序排列的（实际上是按照值得大小排列的），但是不影响我们求解区间和。

C++ 代码

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<long long> Sums;
        Sums.resize(nums.size()+1);

        for (int i = 1;i<=nums.size();++i)
            Sums[i] = Sums[i-1] + nums[i-1];
        int l = 0,r = Sums.size();
        int result = mergesort(l,r,lower,upper,Sums);
        return result;

    }
    int mergesort(int l,int r,int lower,int upper,vector<long long>& Sums){
        if (l==r-1) return 0;


        int mid = (l+r)/2;
        int cnt1 = mergesort(l,mid,lower,upper,Sums);
        int cnt2 = mergesort(mid,r,lower,upper,Sums);
        int res = cnt1+cnt2;
        for (int i = l;i<mid;++i){
            long long  minvalue = Sums[i] + lower;
            long long  maxvalue = Sums[i] + upper;
            vector<long long>::iterator ltr = lower_bound(Sums.begin()+mid,Sums.begin()+r,minvalue);
            vector<long long>::iterator rtr = upper_bound(Sums.begin()+mid,Sums.begin()+r,maxvalue);
            res +=  rtr-ltr;
        }

        vector<long> tmp;
        int idx1 = l,idx2=mid;
        while(idx1<mid&&idx2<r){
            if (Sums[idx1]<Sums[idx2]){
                tmp.push_back(Sums[idx1]);
                idx1++;
            }
            else{
                tmp.push_back(Sums[idx2]);
                idx2++;
            }
        }

        while(idx1<mid){
            tmp.push_back(Sums[idx1]);
            idx1++;
        }

        while(idx2<r){
            tmp.push_back(Sums[idx2]);
            idx2++;
        }

        for (int i = 0;i<tmp.size();++i)
            Sums[i+l]  = tmp[i];


        return res;
    }


};