# 8 lines concise c++ code with explanation

• The idea come from Max Sum of Sub-Matrix No Larger Than K.

``````int countRangeSum(vector<int>& nums, int lower, int upper) {
long long sum=0,ret=0;
multiset<long long> accum={0};
for(auto x:nums){
sum+=x;
auto start=accum.lower_bound(sum-upper),end=accum.upper_bound(sum-lower);
while(start!=end) ret++,start++;
accum.insert(sum);
}
return ret;
}
``````

explanation:
let range sum between `j+1` and `i` be `sum[j][i]`(`j<i`),range sum from `0` to `i` be `sum[i]`.
if `lower<=sum[j][i]<=upper`,then `lower<=sum[i]-sum[j]<=upper`.
then we have

• `sum[i]-sum[j]<=upper`
• `sum[i]-sum[j]>=lower`

thus we can search for `sum[j]` as below:

• lower_bound:`sum[j]>=sum[i]-upper`---use lower_bound() to search for the first previous sum that is `no less` than `sum[i]-upper`.
• upper_bound:`sum[j]>sum[i]-lower`---use upper_bound() to search for the first previous sum that is `bigger` than `sum[i]-lower`.

the time complexities of `insert()`,`upper_bound()` and `lower_bound()` are `O(logn)`.

• That's not O(n log n). Because you're counting the ranges one by one and their number isn't O(n log n).

• Yeah,my fault again,thanks for correct.

• @zoharlee Quite clean solution, thanks for sharing. Voting you up!

• The naive method iterator an array n^2 times
Your method iterator the RB-tree n^2 times

worse than the naive method...

• @zoharlee
use distance can make your code become a little bit quick.
Nice solution anyway.

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

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