C++で解く更新なしの区間和クエリ：累積和による効率的な手法

この記事では、サイズnの整数型配列が与えられたとき、インデックスLからRまでの要素の合計を求めるクエリを複数回処理する問題を扱います。つまり、指定された区間 [L, R] の合計を計算する必要があります。以下に具体例を示します。

入力 : arr[] = {1, 2, 3, 4, 5}
    L = 1, R = 3
    L = 2, R = 4
出力 : 9
    12

入力 : arr[] = {1, 2, 3, 4, 5}
    L = 0, R = 4
    L = 1, R = 2
出力 : 15
    5

問題を解くためのアプローチ

この問題には2つの解法があります。1つは素朴な手法（ブルートフォース）、もう1つは累積和（Prefix Sum）を活用した効率的な手法です。

ブルートフォース（全走査）アプローチ

このアプローチでは、指定された範囲を順番に走査し、その都度合計値を計算して出力します。

実装例

#include<bits/stdc++.h>

using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int); // 配列のサイズ
    int L1 = 1, R1 = 3;
    int L2 = 2, R2 = 4;
    int sum = 0;
    for(int i = L1; i <= R1; i++) // 最初の区間を走査
        sum += arr[i];
    cout << sum << "\n";
    sum = 0;
    for(int i = L2; i <= R2; i++) // 2番目の区間を走査
        sum += arr[i];
    cout << sum << "\n";
}

出力

9
12

コードの解説

このアプローチでは、単純に指定された区間を走査して合計を求めています。単発のクエリであれば、検索の時間計算量はO(N)（Nは配列のサイズ）で十分です。しかし、クエリがQ個与えられる場合、計算量はO(N×Q)に膨れ上がります。残念ながらこの計算量では大きな制約に対応できないため、次により高い制約にも耐えられる効率的なアプローチを見ていきましょう。

効率的なアプローチ（累積和）

このアプローチでは、prefixという名前の累積和配列を事前に構築しておき、その配列を使って各区間の合計を即座に答えます。

実装例

#include<bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int); // 配列のサイズ
    int L1 = 1, R1 = 3;
    int L2 = 2, R2 = 4;
    int sum = 0;
    int prefix[n];
    for(int i = 0; i < n; i++){
        sum += arr[i];
        prefix[i] = sum;
    }

    if(L1) // セグメンテーションフォルトを回避するため
        cout << prefix[R1] - prefix[L1 - 1] << "\n";
    else
        cout << prefix[R1] << "\n";

    if(L2) // セグメンテーションフォルトを回避
        cout << prefix[R2] - prefix[L2 - 1] << "\n";
    else
        cout << prefix[R2] << "\n";
}

出力

9
12

コードの解説

このアプローチでは、prefixという配列に先頭からの累積和を格納していきます。この配列により、任意の区間 [L, R] の合計を「prefix[R] − prefix[L−1]」という引き算1回で求められるようになります。つまり、1回のクエリあたりの時間計算量はO(1)となり、これは理論上最速です。したがって、Q個のクエリが与えられても全体の計算量はO(Q)で済み、非常に大量のクエリにも対応できます。

まとめ

この記事では、累積和配列を使って「更新クエリなしの区間和クエリ」を効率的に解く方法を学びました。素朴な手法と効率的な手法の2つのアプローチを比較しながら、C++での実装例を通じて理解を深めることができたと思います。なお、同じロジックはC言語、Java、Pythonなど他の言語でも同様に実装可能です。この記事が皆さんの学習の一助になれば幸いです。