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

インデックスiからインデックスjまでの要素の合計を計算する必要があります。 iとjのインデックス値で構成されるクエリは複数回実行されます。

Input:arr[] = {5, 6, 3, 4, 1 } i = 1, j =3
Output: 13

説明

6 + 3 + 4 = 13
sum[] = {5, 6+5, 3+6+5, 4+3+6+5, 1+4+3+6+5 }
sum[]={5,11,14,18,19}
sum[j]-sum[i-1]=sum[3]-sum[1-1]= sum[3]-sum[0]=18-5=13

このロジックは、iインデックスからjインデックスまでのループを開始し、それらのインデックス間の要素を合計するという非常に基本的なものです。ただし、それらを追加の変数に格納することはできないため、最後の配列要素とともに配列要素を追加する別の配列を使用します。次に、jインデックスからi-1インデックス値を減算します;

例

#include <iostream>
using namespace std;
int rangeSum(int i, int j, int sum[]) {
   if (i == 0)
      return sum[j];
   return sum[j] - sum[i - 1];
}
int main() {
   int arr[] = { 5, 6, 3, 4, 1 };
   int n=5;
   int sum[5];
   sum[0] = arr[0];
   for (int i = 1; i < n; i++) {
      sum[i] = arr[i] + sum[i - 1];
   }
   cout << rangeSum(1, 3, sum) << endl;
   return 0;
}

出力

13