C++で解く範囲合計クエリ（不変配列）― 累積和による効率的な実装

整数の配列が与えられたとき、インデックス i から j までの範囲に含まれる要素の合計を求めることを考えます。この問題には2つの重要なポイントがあります。1つ目は、配列が不変（イミュータブル）であるため要素が一切変更されないこと、2つ目は、同じ種類のクエリが複数回実行されることです。そのため、大量のクエリが発生しても高速に処理できるよう、実行時間を考慮する必要があります。

例えば、配列が A = [5, 8, 3, 6, 1, 2, 5] のとき、クエリ (A, 0, 3) に対する答えは 5 + 8 + 3 + 6 = 22 となります。

解法のアプローチ：累積和（プレフィックスサム）

この問題を効率的に解くために、以下の手順に従います。

• 補助配列 B を用意します。B[i] には、インデックス 0 から i までの要素の累積合計を格納します。
• 範囲合計のクエリに対しては、B[j] − B[i − 1] を計算して返します。

この手法では、前処理に O(n) の時間がかかりますが、その後の各クエリは O(1) で答えられるため、クエリの数が多い場合に非常に有効です。毎回素朴に範囲内の要素を足し合わせる方法では、1回のクエリに O(n) かかってしまい、クエリが大量にある場合に非効率になります。

実装例

理解を深めるために、以下の C++ の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class NumArray {
   public:
   vector <int> pre;
   NumArray(vector<int>& nums) {
      pre.clear();
      int n = nums.size();
      pre.resize(n);
      for(int i = 0; i < n; i++){
         if(i == 0)pre[0] = nums[0];
         else
         pre[i] = pre[i - 1] + nums[i];
      }
   }
   int sumRange(int i, int j) {
      if(i == 0)return pre[j];
      return pre[j] - pre[i - 1];
   }
};
main(){
   vector<int> v = {5,8,3,6,1,2,5};
   NumArray na(v);
   cout<<na.sumRange(0,2)<<endl;
   cout<<na.sumRange(2,5)<<endl;
   cout<<na.sumRange(0,5)<<endl;
}

入力

[5,8,3,6,1,2,5] で初期化
sumRange(0,2) を呼び出し
sumRange(2,5) を呼び出し
sumRange(0,5) を呼び出し

出力

16
12
25

出力の解説

• sumRange(0, 2) → 5 + 8 + 3 = 16
• sumRange(2, 5) → 3 + 6 + 1 + 2 = 12
• sumRange(0, 5) → 5 + 8 + 3 + 6 + 1 + 2 = 25

計算量

• 前処理（コンストラクタ）：O(n)
• 各クエリ（sumRange）：O(1)
• 空間計算量：O(n)（累積和配列ぶん）

このように、累積和を事前に計算しておくことで、不変配列に対する範囲合計クエリを定数時間で処理できます。なお、配列の要素が更新される可能性がある場合は、セグメント木や Binary Indexed Tree（BIT）などのデータ構造を検討するとよいでしょう。