# 8 line C++ with multiset runs 104ms beats 30%

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

• I tried this solution too.
distance(itlow, itup) uses a for loop to calculate the distance, so the algorithm becomes O(n^2logn) in the worst case.

• Thank your code, it makes me learned the function distance. At first I wanted to use operator - to calculate the distance between two iterators, however the feedback was compile error. So I decided to see the discuss, maybe I can find some similar solution which also uses multiset. Really I found it. By the way in multiset it calculate distance using operator ++, the time complexity is O(n), be careful. Good luck to you .

• I think the worst case should be O(n*(n + 2*n + n)) = O(n^2)

• My mistake. The worst case is O(n(logn + 2logn + n)) = O(n^2)

• The correct analysis of its complexity is actually O(nlogn) + K, which K is the output of the algorithm. So this algorithm's complexity depends on its output. There are many other algorithm that falls into this category too.

• Just explain the solution. The element of the set multiset is the sum of the first n elements in nums . Suppose that x is the element of the set and the next added element of the set is y. And a represents lower and b represents upper. The number of x that satisfies a<=y-x<=b is the value of function distance(). Before we do some thing, change the form a<=y-x<=b and get y-b<=x<=y-a. The soltution is that

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

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