C ++中范围和的计数
假设我们有一个整数数组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<=endandprefix[high]-prefix[i]<=upper），做-
而（j<=endandprefix[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