更新なしの範囲合計クエリを高速に処理するC++プログラム

問題概要

配列のインデックス i から j までの要素の合計を求める必要があります。i と j の値からなるクエリは複数回実行されることを想定します。

入力: arr[] = {5, 6, 3, 4, 1}、i = 1、j = 3
出力: 13

考え方：累積和（Prefix Sum）を活用する

最も単純な方法は、i 番目から j 番目までループで順に足し合わせることですが、クエリの数が多い場合には非常に非効率です。そこで役立つのが累積和です。これは、配列の先頭から順に要素を加算していった値を別の配列に格納しておく手法です。

累積和配列 sum を前計算しておけば、区間 [i, j] の合計は次の式で O(1) で求められます。

sum[j] - sum[i-1]

具体例

6 + 3 + 4 = 13

sum[] = {5, 5+6, 5+6+3, 5+6+3+4, 5+6+3+4+1}
      = {5, 11, 14, 18, 19}

sum[j] - sum[i-1]
      = sum[3] - sum[0]
      = 18 - 5
      = 13

なお、i = 0 の場合は sum[i-1] が存在しないため、sum[j] をそのまま返すようにします。

C++での実装例

#include <iostream>
using namespace std;

// 区間 [i, j] の合計を返す関数
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

計算量のまとめ

• 前計算： 累積和配列の構築に O(n)
• クエリ処理： 1 回あたり O(1)

この手法は、配列の要素が更新されない場合に特に有効です。もし要素の更新も行われる場合は、セグメント木や Binary Indexed Tree（BIT）などのデータ構造を検討するとよいでしょう。