范围总和查询-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