# 327. Count of Range Sum

Given an integer array `nums`, return the number of range sums that lie in `[lower, upper]` inclusive.
Range sum `S(i, j)` is defined as the sum of the elements in `nums` between indices `i` and `j` (`i` ≤ `j`), inclusive.

Note:
A naive algorithm of  O ( n 2) is trivial. You MUST do better than that.

Example:

``````Input: _nums_ = [-2,5,-1], _lower_ = -2, _upper_ = 2,
Output: 3
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.
``````

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

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

j是第一个满足 sums[j] - sums[i] > upper 的下标

k是第一个满足 sums[k] - sums[i] >= lower 的下标

``````class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
vector<long> sums(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); ++i) {
sums[i + 1] = sums[i] + nums[i];
}
return countAndMergeSort(sums, 0, sums.size(), lower, upper);
}
int countAndMergeSort(vector<long>& sums, int start, int end, int lower, int upper) {
if (end - start <= 1) return 0;
int mid = start + (end - start) / 2;
int cnt = countAndMergeSort(sums, start, mid, lower, upper) + countAndMergeSort(sums, mid, end, lower, upper);
int j = mid, k = mid, t = mid;
vector<int> 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;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
cnt += j - k;
}
copy(cache.begin(), cache.begin() + t - start, sums.begin() + start);
return cnt;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/327

Range Sum Query 2D - Immutable

Range Sum Query - Immutable

Reverse Pairs

Count of Smaller Numbers After Self

https://leetcode.com/problems/count-of-range-sum/

https://leetcode.com/problems/count-of-range-sum/discuss/77990/Share-my-solution

https://leetcode.com/problems/count-of-range-sum/discuss/78006/Summary-of-the-Divide-and-Conquer-based-and-Binary-Indexed-Tree-based-solutions

https://leetcode.com/problems/count-of-range-sum/discuss/78030/8-line-multiset-C%2B%2B-solution-(100ms)-also-binary-search-tree-(180ms)-%2B-mergesort(52ms)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation