class Solution {
public:
int mergeSort(vector<long>& sum, int lower, int upper, int low, int high)
{
if(highlow <= 1) return 0;
int mid = (low+high)/2, m = mid, n = mid, count =0;
count =mergeSort(sum,lower,upper,low,mid) +mergeSort(sum,lower,upper,mid,high);
for(int i =low; i< mid; i++)
{
while(m < high && sum[m]  sum[i] < lower) m++;
while(n < high && sum[n]  sum[i] <= upper) n++;
count += n  m;
}
inplace_merge(sum.begin()+low, sum.begin()+mid, sum.begin()+high);
return count;
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
int len = nums.size();
vector<long> sum(len + 1, 0);
for(int i =0; i< len; i++) sum[i+1] = sum[i]+nums[i];
return mergeSort(sum, lower, upper, 0, len+1);
}
};
C++ merge sort solution, very short



@quesder You see here is the thing:
 merge sort here is just to split the whole problem into two separate parts so there is a
count =mergeSort(sum,lower,upper,low,mid) +mergeSort(sum,lower,upper,mid,high);
but the sums that belong to the specified
lower and higher
can start from theleft half
to theright half
(you must already be very clear about the prefixsum, right? then this is not tricky for you) after the merge sort the left and right parts are sorted, so for each left sum
a
, what we should do is to search for range that the prefixsums in the rightb
can meet the conditionlower <= ba <= higher
and then that range is the possible choice we have in the right part for that single index.

@LHearen
Thanks. Another question, though may be silly. Why do we return 0 if high  low <= 1?
If it is 1, shouldn't we try whether sum[high]sun[end] is in range or not?

@quesder
mergeSort(sum, lower, upper, 0, len+1);
This statement, do you notice it? the last iterator is
excluded
so oncehighlow<=1
then there is only at most one element in the range.


Here is java version of your method:
class Solution { public int countRangeSum(int[] nums, int lower, int upper) { if(nums==null  nums.length<1){ return 0; } long[] sums = new long[nums.length]; long sum = 0; for(int i=0;i<nums.length;i++){ sum+=nums[i]; sums[i] = sum; } int higher = upper; return merger(sums,0,sums.length1,lower,higher); } public int merger(long[] sums,int start,int end,int lower,int higher){ if(start>end){ return 0; }else if(start==end){ if(sums[start]>=lower&&sums[end]<=higher){ return 1; } return 0; } int mid = (start+end)>>>1; int count=merger(sums,start,mid,lower,higher)+merger(sums,mid+1,end,lower,higher); int lowerIndex = mid+1; int higherIndex = mid+1; for(int i=start;i<=mid;i++){ while(lowerIndex<=end&&sums[lowerIndex]sums[i]<lower){ lowerIndex++; } while(higherIndex<=end&&sums[higherIndex]sums[i]<=higher){ higherIndex++; } count+=(higherIndexlowerIndex); } mergerHelper(sums,start,mid,end); return count; } public void mergerHelper(long[] sums,int start,int mid,int end){ int i = start; int j = mid+1; long[] copy = new long[endstart+1]; int p=0; while(i<=mid&&j<=end){ if(sums[i]<sums[j]){ copy[p++]=sums[i++]; }else{ copy[p++] = sums[j++]; } } while(i<=mid){ copy[p++]=sums[i++]; } while(j<=end){ copy[p++] = sums[j++]; } System.arraycopy(copy,0,sums,start,endstart+1); } }

I have the same question.
When when high  low == 1, for example, we have 2, whose index is 3
and 2 is in the range of [lower,upper], if you return 0, you can't get [3,3]. Instead, we should judge whether it's in [lower, upper], and return 1 or 0.Am I correct ? Please tell me if I am wrong.