更新なしの範囲合計クエリをC++で高速に解く方法｜累積和の活用

本記事では、配列のインデックスiからjまでの要素の合計を求める方法を解説します。これはいわゆる「範囲合計クエリ（レンジクエリ）」と呼ばれる典型的な問題です。

最も単純な方法は、インデックスiからjまでループを回して順番に合計を足していくことです。しかし、この種の範囲クエリは複数回実行されることが前提となるため、クエリごとに毎回ループで計算していると処理時間が大きくなってしまいます。

そこで有効なのが累積和を事前に計算しておく手法です。累積和を前計算しておけば、以降の範囲合計はどの範囲でも定数時間O(1)で求められます。具体的なアルゴリズムを見ていきましょう。

アルゴリズム

rangeSum(arr, i, j)

begin
    c_arr := 配列arrの累積和
    if i = 0 then
        return c_arr[j]
    else
        return c_arr[j] − c_arr[i−1]
end

考え方のポイント

• c_arr[i] には「先頭（インデックス0）からインデックスiまでの要素の合計」が格納されます。
• インデックスiからjまでの合計は、「先頭からjまでの合計」から「先頭からi−1までの合計」を引けば求まります。つまり c_arr[j] − c_arr[i−1] です。
• iが0の場合は引く対象が存在しないため、c_arr[j] がそのまま答えになります。

C++での実装例

#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];
    }
}

// 範囲 [i, j] の合計を返す関数
int rangeSum(int c_arr[], int i, int j){
    if(i == 0){
        return c_arr[j];
    }
    return c_arr[j] - c_arr[i-1];
}

int 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); // 累積和を取得
    cout << "インデックス(2〜5)の範囲合計: " << rangeSum(c_arr, 2, 5) << endl;
    cout << "インデックス(0〜3)の範囲合計: " << rangeSum(c_arr, 0, 3) << endl;
    cout << "インデックス(4〜7)の範囲合計: " << rangeSum(c_arr, 4, 7) << endl;
}

出力結果

インデックス(2〜5)の範囲合計: 128
インデックス(0〜3)の範囲合計: 49
インデックス(4〜7)の範囲合計: 176

計算量のまとめ

• 前計算（累積和の構築）：O(n)
• 範囲合計クエリ1回あたり：O(1)

素朴なループで範囲合計を求める場合、1回のクエリに最大O(n)の時間がかかります。一方、累積和を使えば前計算のコストを一度払うだけで、以降は何回クエリを実行しても定数時間で答えを得られます。配列の更新が行われず、範囲合計の問い合わせが大量にある場合に特に効果的な手法です。