# [recommend for beginners] C++ implementations of the top-voted-solution

• ``````class Solution {
public:
/***   O(N^2)  Solution     ***/
int countRangeSum(vector<int>& nums, int lower, int upper) {
int size_nums=nums.size();
vector<long> sums(size_nums+1, 0);
for(int i=0; i<size_nums; i++){
sums[i+1]=sums[i]+nums[i];
}
int result=0;
for(int i=0; i<size_nums; i++){
for(int j=i+1; j<=size_nums; j++){
int temp=sums[j]-sums[i];
if(temp >= lower && temp <= upper)  result++;
}
}
return result;
}

/***   O(N*logN)  Solution     ***/
int countRangeSum(vector<int>& nums, int lower, int upper) {
int size_nums=nums.size();
vector<long> sums(size_nums+1, 0);
for(int i=0; i<size_nums; i++)   sums[i+1]=sums[i]+nums[i];
return help(sums, 0, size_nums+1, lower, upper);
}

int help(vector<long> &sums, int start, int end, int lower, int upper){
/***  end condition  ***/
if(end - start <= 1) return 0;
/***  recursive devidely  ***/
int mid=(start+end)/2;
int count=help(sums, start, mid, lower, upper)
+ help(sums, mid, end, lower, upper);
int j=mid, k=mid, t=mid;
vector<long> cache(end-start, 0);
for(int i=start, r=0; i<mid; i++, r++){
while(k<end && sums[k]-sums[i] < lower) k++;
while(j<end && sums[j]-sums[i] <= upper) j++;
/***  merge sorting parts  ***/
while(t<end && sums[t] < sums[i])  cache[r++]=sums[t++];
cache[r]=sums[i];
count+=j-k;
}
//copy the merge sorted array to the original sums
for(int i=0; i<t-start; i++)  sums[start+i]=cache[i];
return count;
}
};``````

• ``````class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int _size=nums.size();
if(_size==0)  return 0;
int result=0;
vector<int> sum(_size+1, 0);
for(int i=1; i<=_size; i++){
sum[i]=sum[i-1]+nums[i-1];
}
for(int i=0; i<=_size-1; i++){
for(int j=i+1; j<=_size; j++){
int temp=sum[j]-sum[i];
if(temp>=lower && temp<=upper) result++;
}
}
return result;
}
};``````

• this method is by building a binary-prefix-sum-tree. The root record sum[0,0], the other node in the tree record sum[0, i] in the binary search form.
So when we search the

``````        #CNT =  sum[i]-sum[j] (j<i)   subject to.    lower <=sum[i]-sum[j] <= upper
``````

For each sum[i], we can do the search in O(logN) time. so the overall time is

``````     O(logN*N)
``````

Here is the code : we count the #CNT ended by sum[i] i=1...n

``````  class Node{
public:
long long val;
int cnt;
Node *left, *right;
Node(long long v):val(v), cnt(1), left(NULL), right(NULL) {}
};

class Tree{
public:
Tree():root(NULL){}
~Tree() { freeTree(root); }

void Insert(long long val){
Insert(root, val);
}

int  LessThan(long long sum, int val){
return LessThan(root, sum, val, 0);
}

private:
Node* root;
void Insert(Node* &root, long long val){
if(!root){
root=new Node(val);
return;
}
root->cnt++;
if(val<root->val){
Insert(root->left, val);
}else if(val>root->val){
Insert(root->right, val);
}
}

int LessThan(Node* root, long long sum, int val, int res){
if(!root)  return res;
if(sum-root->val < val){
res+=(root->cnt-(root->left ? root->left->cnt : 0));
return LessThan(root->left, sum, val, res);
}else if(sum-root->val > val){
return LessThan(root->right, sum, val, res);
}else{
return res+(root->right ? root->right->cnt : 0);
}
}

void freeTree(Node* root){
if(!root) return;
if(root->left)  freeTree(root->left);
if(root->right) freeTree(root->right);
delete root;
}
};

class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
Tree tree;
tree.Insert(0);
long long sum=0;
int res=0;
for(int n:nums){
sum+=n;
int lcnt=tree.LessThan(sum, lower);
int hcnt=tree.LessThan(sum, upper+1);
res+=(hcnt-lcnt);
tree.Insert(sum);
}
return res;
}
};``````

• ``````class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int size=nums.size();
if(size==0)  return 0;
vector<long> sums(size+1, 0);
for(int i=0; i<size; i++)  sums[i+1]=sums[i]+nums[i];
return help(sums, 0, size+1, lower, upper);
}

/*** [start, end)  ***/
int help(vector<long>& sums, int start, int end, int lower, int upper){
/*** only-one-element, so the count-pair=0 ***/
if(end-start<=1)  return 0;
int mid=(start+end)/2;
int count=help(sums, start, mid, lower, upper)
+ help(sums, mid, end, lower, upper);

int m=mid, n=mid, t=mid, len=0;
/*** cache stores the sorted-merged-2-list ***/
/*** so we use the "len" to record the merged length ***/
vector<long> cache(end-start, 0);
for(int i=start, s=0; i<mid; i++, s++){
/*** wrong code: while(m<end && sums[m++]-sums[i]<lower);  ***/
while(m<end && sums[m]-sums[i]<lower) m++;
while(n<end && sums[n]-sums[i]<=upper) n++;
count+=n-m;
/*** cache will merge-in-the-smaller-part-of-list2 ***/
while(t<end && sums[t]<sums[i]) cache[s++]=sums[t++];
cache[s]=sums[i];
len=s;
}

for(int i=0; i<=len; i++)  sums[start+i]=cache[i];
return count;
}
};``````

• This problem can be solved in O(NlogN) using the merging sorting based method ..

233333333333

Code :

``````class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int size_nums = nums.size();
vector<long> sums(size_nums+1, 0);
for(int i = 0; i < size_nums; i++) {
sums[i+1] = sums[i] + nums[i];
}
return help(sums, 0, size_nums+1, lower, upper);
}

/** end is open field [start, end) **/
int help(vector<long>& sums, int start, int end, int lower, int upper) {
if(end - start <= 1)  return 0;
int mid = (start + end) / 2;
int count = help(sums, start, mid, lower, upper) + help(sums, mid, end, lower, upper);

int left = mid, right = mid, cur = mid;

vector<long> cache(end - start, 0);
int cache_index = 0;
for(int i = start, j = mid; i < mid; i++) {
while(left < end && sums[left] - sums[i] < lower)  left++;
while(right < end && sums[right] - sums[i] <= upper) right++;
/** merge sort only put the smaller number before **/
while(j < end && sums[i] >= sums[j])  cache[cache_index++] = sums[j++];
cache[cache_index++] = sums[i];
count += (right - left);
}

for(int i = 0; i < cache_index; i++) {
sums[start + i] = cache[i];
}

return count;
}
};``````

• Here is a solution refered to the Lintcode ..

The key idea is to use the

``````lower_bound    &    upper_bound
``````

To find all the index that sum range smaller than the start value, which is the left iterator.
Similarly , we find the index the sum range smaller than the end value, which is the right iterator.
So the range [left + 1, right] is just the range satisify the condition.

``````class Solution {
public:
/**
* @param A an integer array
* @param start an integer
* @param end an integer
* @return the number of possible answer
*/
int subarraySumII(vector<int>& A, int start, int end) {
// sum_from_start[i] denotes sum for 0 ~ i - 1.
vector<int> sum_from_start(A.size() + 1);
partial_sum(A.cbegin(), A.cend(), sum_from_start.begin() + 1);

int result = 0;
for (int j = 0; j < A.size(); ++j) {
const auto left = lower_bound(sum_from_start.cbegin(),
sum_from_start.cbegin() + j + 1,
sum_from_start[j + 1] - end);
const auto right = upper_bound(sum_from_start.cbegin(),
sum_from_start.cbegin() + j + 1,
sum_from_start[j + 1] - start);
result += (right - sum_from_start.cbegin()) -
(left - sum_from_start.cbegin());
}

return result;
}
};``````

• Your solution is incorrect, lower_bound works only on a sorted array.

• I strong recommend this multiset based solution !!!

``````class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int result = 0;
long long sum = 0;
multiset<long long> sums;
sums.insert(0);
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
result += distance(sums.lower_bound(sum - upper), sums.upper_bound(sum - lower));
sums.insert(sum);
}
return result;
}
};``````

• @RainbowSecret I would say your solution is too complex.

• @fight.for.dream I think this solution is still O(n^2), because although lower_bound/upper_bound method is O(logn), the distance operation for multiset is O(n). Then the total complexity is still O(n^2).

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