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:

Input: nums = [-2,5,-1], lower = -2, upper = 2,

Output: 3 

Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

分析：题目意思是统计处于【lower,upper】的区间和个数。

1.采用分治法，利用归并排序

class Solution {public:    int ans=0;    int low, up;    void merge(long long s[], int l, int m, int r) {        int x=m+1,y=m+1;        for(int z = l; z <= m; z++) {                      while(x<=r&&s[x]-s[z]
       
        =r) return;        solve(s, l, m);        solve(s, m+1, r);        merge(s,l,m,r);    }    int countRangeSum(vector
        
         & nums, int lower, int upper) {        low = lower;        up = upper;        int len = nums.size();        if(len==0) return 0;        long long s[10005]={0};        for(int i = 1; i <= len; i++) s[i] = s[i-1]+nums[i-1];           solve(s,0,len);        return ans;    }};