假设我们有一个整数数组nums，我们必须找到位于范围[lower，upper]（包括下限和下限）的范围总和的数量。范围总和S(i,j)定义为从索引i到索引i（其中i≤j）的元素的总和。
因此，如果输入为[-3,6，-1]，lower = -2和upper = 2，则结果将为2，因为范围为[0,2]，总和为2，[2， 2]，总和为-2。
为了解决这个问题，我们将遵循以下步骤-
定义一个功能mergeIt()，它将使用数组前缀，开始，中间，结束，较低，较高，
i：=开始，j：=中+ 1
温度：=结束-开始+ 1
低：=中+ 1，高：=中+ 1
k：= 0
定义大小为temp的数组arr。
当我<=中时，做-
arr [k]：=前缀[j]
（将j增加1）
（将k增加1）
高一
低1
而（低<=结束和前缀[低]-前缀[i] <较低），则执行-
while（high <= end and prefix [high]-prefix [i] <= upper），做-
而（j <= end and prefix [j] <prefix [i]），则-
arr [k]：=前缀[i]
（将i增加1）
（将k增加1）
计数：=计数+高-低
当j <=结束时，-
arr [k]：=前缀[j]
（将k增加1）
（将j增加1）
对于初始化i：= 0，当i <temp时，更新（将i增加1），执行-
前缀[开始]：= arr [i]
（增加1开始）
定义一个功能merge()，它将使用prefix []，开始，结束，较低，较高，
如果开始> =结束，则返回
中：=开始+（结束-开始）
调用函数merge（前缀，开始，中，下，上）
调用函数merge（prefix，mid + 1，end，lower，upper）
调用功能mergeIt(prefix,start,mid,end,lower,upper)
从主要方法中，执行以下操作-
n：= nums的大小
计数：= 0
定义大小为n + 1的数组前缀。
前缀[0]：= 0
对于初始化i：= 1，当i <= n时，更新（将i增加1），-
prefix [i]：=前缀[i-1] + nums [i-1]
调用函数merge(prefix,0,n,lower,upper)
返回计数
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int count = 0;
void mergeIt(lli prefix[], lli start ,lli mid, lli end, lli lower, lli upper){
lli i = start, j = mid + 1;
lli temp = end - start + 1;
lli low = mid + 1, high = mid + 1;
lli k = 0;
lli arr[temp];
while(i <= mid){
while(low <= end && prefix[low] - prefix[i] < lower) low++;
while(high <= end && prefix[high] - prefix[i] <= upper) high++;
while(j<= end && prefix[j] < prefix[i]){
arr[k] = prefix[j];
j++;
k++;
}
arr[k] = prefix[i];
i++;
k++;
count += high - low;
}
while(j <= end){
arr[k] = prefix[j];
k++;
j++;
}
for(i = 0; i < temp; i++){
prefix[start] = arr[i];
start++;
}
}
void merge(lli prefix[], lli start, lli end, lli lower, lli upper){
if(start >= end)return;
lli mid = start + (end - start) / 2;
merge(prefix, start, mid, lower, upper);
merge(prefix, mid + 1, end, lower, upper);
mergeIt(prefix, start, mid, end, lower, upper);
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
lli n = nums.size();
count = 0;
lli prefix[n + 1];
prefix[0] = 0;
for(lli i = 1; i <= n; i++){
prefix[i] = prefix[i - 1] + nums[i - 1];
}
merge(prefix, 0, n, lower, upper);
return count;
}
};
main(){
Solution ob;
vector<int> v = {-3,6,-1};
cout << (ob.countRangeSum(v, -2, 2));
}{-3,6,-1}
-2
2输出结果
2