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);
}
};
8 line C++ with multiset runs 104ms beats 30%


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 .

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<=yx<=b is the value of function distance(). Before we do some thing, change the form a<=yx<=b and get yb<=x<=ya. 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(offsetnums[i]); auto up=set.upper_bound(offsetlower),low=set.lower_bound(offsetupper); sum+=distance(low,up); } return (int)sum; } };