【C++】配列の指定範囲の平均値を求める方法：累積和で効率化する解法

この問題では、n個の整数からなる配列とm個のクエリが与えられます。各クエリで指定された範囲の平均値の整数部分（小数点以下は切り捨て）を計算するプログラムを作成するのがタスクです。

具体例を使って問題を確認しましょう。

入力 −

array = {5, 7, 8, 9, 10}
m = 2; [0, 3], [2, 4]

出力 −

7
9

この問題を解く方法は大きく分けて2つあります。ひとつは素直に直接計算する方法、もうひとつは累積和（prefix sum）を活用する方法です。

直接計算のアプローチ：各クエリに対して、範囲の開始インデックスから終了インデックスまでループ処理を行い、該当する要素をすべて加算してから要素数で割ります。この方法でも正しい結果は得られますが、クエリごとに範囲内の要素を毎回足し直すため、計算量はO(n)となり、クエリが多くなると非効率です。

累積和（Prefix Sum）を使う方法

このアプローチでは、あらかじめ「配列の先頭からi番目のインデックスまでの要素の合計」を格納する累積和配列を計算しておきます。つまり、prefixSum(4)はインデックス4までの全要素の合計を表します。

この累積和配列を利用すれば、各クエリの平均値は次の式でO(1)で求められます。

Mean = (prefixSum[upper] - prefixSum[lower-1]) / (upper - lower + 1)

upperとlowerはクエリで指定された範囲のインデックスです。lowerが0の場合は、prefixSum(lower-1)を0として扱います。

前処理にO(n)かかりますが、以降の各クエリへの応答が定数時間で済むため、クエリ数が多い場合に大幅な高速化が期待できます。

サンプルプログラム

この解法の動作を示すC++プログラムは以下の通りです。

#include <iostream>
#define MAX 100
using namespace std;
int prefixSum[MAX];
void initialisePrefixSum(int arr[], int n) {
   prefixSum[0] = arr[0];
   for (int i = 1; i < n; i++)
   prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int queryMean(int l, int r) {
   int mean;
   if (l == 0)
      mean =(prefixSum[r]/(r+1));
   else
      mean =((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1));
      return mean;
}
int main() {
   int arr[] = {5, 7, 8, 9, 10 };
   int n = sizeof(arr) / sizeof(arr[0]);
   initialisePrefixSum(arr, n);
   cout<<"1番目のクエリの平均: "<<queryMean(1, 4)<<endl;
   cout<<"2番目のクエリの平均: "<<queryMean(2, 4)<<endl;
   return 0;
}

実行結果

1番目のクエリの平均: 8
2番目のクエリの平均: 9

このように、累積和を事前に構築しておくことで、範囲の合計を差分だけで即座に求められ、多数のクエリが発生する場面でも効率的に平均値を計算できます。