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)`

.