更新なしの範囲合計クエリ用のC++プログラム？

ここでは、配列内のインデックスiからインデックスjまでの要素の合計を取得する方法を説明します。これは基本的に範囲クエリです。インデックスiからjまで1つのループを実行し、合計を計算するだけで、タスクは簡単です。ただし、この種の範囲クエリが複数回実行されることに注意する必要があります。したがって、上記の方法を使用すると、かなりの時間がかかります。より効率的な方法を使用してこの問題を解決するには、最初に累積合計を取得し、次に範囲合計を一定時間で見つけることができます。アイデアを得るためのアルゴリズムを見てみましょう。

アルゴリズム

rangeSum（arr、i、j）

begin
   c_arr := cumulative sum of arr
   if i = 0, then
      return c_arr[j];
      return c_arr[j] – c_arr[i-1]
end

例

#include<iostream>
using namespace std;
void cumulativeSum(int c_arr[], int arr[], int n){
   c_arr[0] = arr[0];
   for(int i = 1; i<n; i++){
      c_arr[i] = arr[i] + c_arr[i-1];
   }
}
int rangeSum(int c_arr[], int i, int j){
   if( i == 0){
      return c_arr[j];
   }
   return c_arr[j] - c_arr[i-1];
}
main() {
   int data[] = {5, 4, 32, 8, 74, 14, 23, 65};
   int n = sizeof(data)/sizeof(data[0]);
   int c_arr[n];
   cumulativeSum(c_arr, data, n); //get cumulative sum
   cout << "Range sum from index (2 to 5): " << rangeSum(c_arr, 2, 5) << endl;
   cout << "Range sum from index (0 to 3): " << rangeSum(c_arr, 0, 3) << endl;
   cout << "Range sum from index (4 to 7): " << rangeSum(c_arr, 4, 7) << endl;
}

出力

Range sum from index (2 to 5): 128
Range sum from index (0 to 3): 49
Range sum from index (4 to 7): 176