C++で指定範囲の要素の合計からサム配列（sum-array）を作成する方法

問題概要

整数のみを含む配列 arr[ ] と、奇数 sum が与えられます。このとき、次のような合計配列 arr_2[ ] を作成することが目的です。

各要素 arr_2[i] は、「arr[ ] 内の直前 sum/2 個の要素 ＋ arr[i] 自身 ＋ 直後 sum/2 個の要素」の合計となります。なお、sum が 1 の場合は arr_2[i] = arr[i] となります。

入力例と出力例

例1

入力：

arr[] = { 4, 1, 7, 5, 2, 9, 6, 2, 1 }、sum = 3

出力：

指定範囲の要素の合計によるサム配列の構築結果： 5 12 13 14 16 17 17 9 3

説明：

サム配列は以下のように構築されます：
arr_2[0] = arr[0] + arr[1] = 4 + 1 = 5
arr_2[1] = arr[0] + arr[1] + arr[2] = 4 + 1 + 7 = 12
arr_2[2] = arr[1] + arr[2] + arr[3] = 1 + 7 + 5 = 13
arr_2[3] = arr[2] + arr[3] + arr[4] = 7 + 5 + 2 = 14
arr_2[4] = arr[3] + arr[4] + arr[5] = 5 + 2 + 9 = 16
arr_2[5] = arr[4] + arr[5] + arr[6] = 2 + 9 + 6 = 17
arr_2[6] = arr[5] + arr[6] + arr[7] = 9 + 6 + 2 = 17
arr_2[7] = arr[6] + arr[7] + arr[8] = 6 + 2 + 1 = 9
arr_2[8] = arr[7] + arr[8] = 2 + 1 = 3

例2

入力：

arr[] = { 1, 2, 3, 4, 5 }、sum = 5

出力：

指定範囲の要素の合計によるサム配列の構築結果： 6 10 15 14 12

説明：

サム配列は以下のように構築されます：
arr_2[0] = arr[0] + arr[1] + arr[2] = 1 + 2 + 3 = 6
arr_2[1] = arr[0] + arr[1] + arr[2] + arr[3] = 1 + 2 + 3 + 4 = 10
arr_2[2] = arr[0] + arr[1] + arr[2] + arr[3] + arr[4] = 1 + 2 + 3 + 4 + 5 = 15
arr_2[3] = arr[1] + arr[2] + arr[3] + arr[4] = 2 + 3 + 4 + 5 = 14
arr_2[4] = arr[2] + arr[3] + arr[4] = 3 + 4 + 5 = 12

アルゴリズム（スライディングウィンドウ方式）

ここで紹介するプログラムでは、スライディングウィンドウ（sliding window）の考え方を利用します。前のウィンドウの合計値に対して、右側に新しい要素を加え、左端の要素を取り除くだけで次の合計を求められるため、毎回ゼロから計算するよりもはるかに効率的です。

• 整数配列 arr[ ] と値 sum を入力として受け取ります。
• 関数 sum_array(int arr[], int size, int sum) が、指定範囲の要素の合計からなるサム配列を返します。
• 初期カウント count を 0 とします。
• サム配列を arr_2[size] として用意します。
• temp = sum / 2 + 1 とします。
• 先頭から temp 個の要素（インデックス 0 ～ temp-1）を count に加算し、arr_2[0] = count とします。
• 以降の要素については、for ループで i = 1 ～ size-1 まで走査します。
• temp_1 = i − (sum / 2) − 1 とし、temp_1 ≥ 0 であれば count から arr[temp_1] を減算します。
• temp_2 = i + (sum / 2) とし、temp_2 ＜ size であれば count に arr[temp_2] を加算します。
• arr_2[i] = count とします。
• ループ終了時には、arr_2[ ] が求めるサム配列になっています。
• 最後に for ループでサム配列 arr_2[ ] を出力します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
void sum_array(int arr[], int size, int sum){
    int count = 0;
    int arr_2[size];
    int temp = sum / 2 + 1;
    for (int i = 0; i < temp; i++){
        count = count + arr[i];
    }
    arr_2[0] = count;
    for (int i = 1; i < size; i++){
        int temp_1 = i - (sum / 2) - 1;
        if (temp_1 >= 0){
            count = count - arr[temp_1];
        }
        int temp_2 = i + (sum / 2);
        if (temp_2 < size){
            count = count + arr[temp_2];
        }
        arr_2[i] = count;
    }
    cout<<"Construction of sum-array with sum of elements in given range are: ";
    for (int i = 0; i < size; i++){
        cout<< arr_2[i] << " ";
    }
}
int main(){
    int arr[] = { 4, 1, 7, 5, 2, 9, 6, 2, 1 };
    int sum = 3;
    int size = sizeof(arr) / sizeof(int);
    sum_array(arr, size, sum);
    return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

Construction of sum-array with sum of elements in given range are: 5 12 13 14 16 17 17 9 3

計算量について

スライディングウィンドウを活用することで、各要素ごとに合計を最初から計算し直す必要がなくなります。素朴な方法では各要素につき最大 sum 個の要素を足すため O(n × sum) の時間がかかりますが、この手法では各ステップで加算・減算を1回ずつ行うだけなので、全体の時間計算量は O(n) に抑えられます。大規模な配列を扱う場合に特に有効なアプローチです。