範囲合計クエリ-C++の不変

整数の配列があるとします。インデックスiからjまでの要素の合計を見つける必要があります。配列は不変であるため、要素は変更されず、そのようなクエリが複数存在することに注意する必要があります。そのため、多数のクエリの実行時間を気にする必要があります。配列がA=[5、8、3、6、1、2、5]のようであるとすると、クエリが（A、0、3）の場合、5 + 8 + 3 + 6=22になります。

これを解決するには、次の手順に従います-

• 1つの配列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