# C++ merge sort solution, very short

• ``````class Solution {
public:
int mergeSort(vector<long>& sum, int lower, int upper, int low, int high)
{
if(high-low <= 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);
}
};``````

• very nice solution !
very nice solution !
very nice solution !
.

• inplace_merge？？？

int mid = (low+high)/2

use

`` int mid = low + (high-low)/2``

• Is each mergeSort taking O(n^2)?

``````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;
}
``````

Is this part taking O(n^2)?

• no, only O(n), m and n at most plus mid times

• i from low to mid; each time m and n can go from mid to high; so O(n/2)*O(n/2)=O(n^2). Am I wrong?

• m and n will keep increase rather than start from beginning each time, that means though for loop will run mid times, but while loop will at most run mid times too.

• @508618087qq.com Quite clean one! Thanks, voting you up!

• why can you do merge sort on the sum vector? That will change the order of the elements, why can you still use sum[m] -sum[i] as a criteria to increase m? Thanks.

• @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 the `left half` to the `right half` (you must already be very clear about the prefix-sum, 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 prefix-sums in the right `b` can meet the condition `lower <= b-a <= 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 once `high-low<=1` then there is only at most one element in the range.

• @508618087qq.com
Brilliant!

• 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.length-1,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+=(higherIndex-lowerIndex);
}
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[end-start+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,end-start+1);
}
}
``````

• This one should be best solution!!!

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.