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 arraynums. 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;
}
KejiTech 