范围总和查询-C ++中的不可变
假设我们有一个整数数组。我们必须找到从索引i到j的元素之和。我们必须记住两件事，数组将是不可变的，因此元素不会被更改，并且会有多个此类查询。因此，我们必须考虑大量查询的执行时间。假设数组类似于A=[5，8，3，6，1，2，5]，那么如果查询为(A,0,3)，则它将为5+8+3+6=22。
为了解决这个问题，我们将遵循以下步骤-
取一个数组B。B[i]将存储从0到i的元素之和
对于查询，请执行B[j]–B[i–1]
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class NumArray {
public:
vector <int> pre;
NumArray(vector<int>& nums) {
pre.clear();
int n = nums.size();
pre.resize(n);
for(int i = 0; i < n; i++){
if(i == 0)pre[0] = nums[0];
else
pre[i] = pre[i - 1] + nums[i];
}
}
int sumRange(int i, int j) {
if(i == 0)return pre[j];
return pre[j] - pre[i - 1];
}
};
main(){
vector<int> v = {5,8,3,6,1,2,5};
NumArray na(v);
cout<<na.sumRange(0,2)<<endl;
cout<<na.sumRange(2,5)<<endl;
cout<<na.sumRange(0,5)<<endl;
}输入值
Initialize it with [5,8,3,6,1,2,5] Call sumRange(0,2) sumRange(2,5) sumRange(0,5)
输出结果
16 12 25