# Count of Range Sums

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. A naïve algorithm of O(n2) is trivial. You MUST do better than that.

Difficulty: Very hard.

### Input

The first line contains 3 integers separated by spaces:

• `n`, representing the length of the integer array `nums`.
• `lower`.
• `upper`.

The second line is the integer array `nums`, containing `n` integers with neighboring elements separated by a space.

At the end of each line, there are no extra spaces, and there is a `\n`.

### Output

One line containing 1 integer, which is the number of range sums that lie in `[lower, upper]` inclusive.

### Example

Input:

`3 -2 2 `

`-2 5 1`

Output:

`3`

Explanation:

`nums` = [-2,5,-1], `lower` = -2, `upper` = 2.

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

### Solution: C++

```#include<stdlib.h>
#include<stdio.h>
#include<iostream>

using namespace std;

// merge the two ordered arrays b and c into the original array a
void merge(long long int a[], int l, int m, int r){
int n1 = m - l + 1; //size of array b
int n2 =  r - m; //size of array c

// create temp arrays of b and c
long long int B[n1], C[n2];

int i, j;
// copy arrays a and b into temp arrays B and C
for (i = 0; i < n1; i++)
B[i] = a[l + i];
for (j = 0; j < n2; j++)
C[j] = a[m + 1 + j];

// merge the temp arrays A and B back into array a in the right position
i = 0; // index of B
j = 0; // index of C
int idx = l; // index of the array a
while (i < n1 && j < n2){
if (B[i] <= C[j]){
a[idx] = B[i];
i++;
}
else{
a[idx] = C[j];
j++;
}
idx++;
}

// copy the remaining elements of B into a
while (i < n1) {
a[idx] = B[i];
i++;
idx++;
}

// copy the remaining elements of C into a
while (j < n2) {
a[idx] = C[j];
j++;
idx++;
}
}

int merge_solve(int l, int r, long long int lower, long long int upper, long long int p[]){ //2T(n/2)+O(n)
if (l < r){
int m = l+(r-l)/2; //index to split the the array in two parts
int s1 = merge_solve(l, m, lower, upper, p); //range sums in first half
int s2 = merge_solve(m+1, r, lower, upper, p); //range sums in second half

int range_sums=0;
//j = iterator for second half
int i1=l; //i1 = iterator upper bound first half
int i2=l; //i2 = iterator lower bound first half
// find all (i,j) indexes satisfying the constraints
for(int j=m+1;j<=r;j++){
for(;i1<=m && p[i1]+lower<=p[j];i1++);
for(;i2<=m && p[j]>p[i2]+upper;i2++);
range_sums+=i1-i2;
}

merge(p, l, m, r); //same as mergesort
return range_sums+s1+s2;
}
// l==r
return lower<=p[l] && p[l]<=upper;
}

int main(){
int n;
cin>>n;  //length of the array
long long int lower; //sum lower bound
cin>>lower;
long long int upper; //sum upper bound
cin>>upper;
int nums[n];
for(int i=0; i<n; i++)
cin>>nums[i];

long long int p[n];
p[0]=nums[0];
for(int i=1;i<n;i++){ //O(n)
p[i]=p[i-1]+nums[i];
}

int n_range_sum = merge_solve(0, n-1, lower, upper, p);
cout<<n_range_sum;
}
```

## One thought on “Count of Range Sums”

1. Liu Yan Ping says:

Very difficult to understand.

Like