【C++】m回の範囲加算操作後の配列の最大値を求めるアルゴリズム

この記事では、0で初期化されたN個の要素を持つ配列arr[]に対して、m回の範囲加算(インクリメント)操作を実行した後の、配列内の最大値を求めるプログラムをC++で作成します。

問題の概要

配列に対して、次のような形式の範囲加算操作をm回実行します。

update[L, R, K] = 区間[L, R]に含まれるすべての要素に値Kを加算する

m回の操作をすべて完了した後、配列の中で最も大きな値を持つ要素を見つけることが目的です。

入力例

N = 6, m = 4
Update[][] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}}

出力例

34

解説

arr[] = {0, 0, 0, 0, 0, 0}
Update 1 {1, 4, 12} : arr[] = {0, 12, 12, 12, 12, 0}
Update 2 {0, 3, 5} : arr[] = {5, 17, 17, 17, 12, 0}
Update 3 {1, 5, 7} : arr[] = {5, 24, 24, 24, 19, 7}
Update 4 {3, 5, 10} : arr[] = {5, 24, 24, 34, 29, 17}

すべての操作が終わった時点で、配列内の最大値は34であることが分かります。

解法1:素朴なシミュレーション

最もシンプルな方法は、各操作のたびに指定された区間の要素を実際に更新していき、すべての操作が完了した後に配列を走査して最大値を求めるというものです。

#include<iostream>
using namespace std;

int findmax(int arr[], int N){
    int maxVal = 0;
    for(int i = 0; i < N; i++){
        if(maxVal < arr[i]){
            maxVal = arr[i];
        }
    }
    return maxVal;
}

void updateVal(int arr[], int L, int R, int K){
    for(int i = L; i <= R; i++){
        arr[i] += K;
    }
}

int main(){
    int N = 5;
    int arr[N] = {0};
    int M = 4;
    int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}};
    for(int i = 0; i < M; i++){
        updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]);
    }
    cout<<"The maximum value in the array after "<<M<<" range increment operations is "<<findmax(arr, N);
    return 0;
}

出力

The maximum value in the array after 4 range increment operations is 34

この方法は直感的で理解しやすい反面、クエリごとに区間全体を走査する必要があるため、計算量はO(m × N)となります。Nやmが大きくなると処理時間が急激に増加するという弱点があります。

解法2:差分配列(imos法)による高速化

より効率的なのが「差分配列」と呼ばれる手法です。各範囲加算操作に対して、次の2点だけを更新します。

• L番目の要素にKを加算する
• R+1番目の要素からKを減算する

すべての操作終了後、配列の先頭から累積和を計算すると、各区間への加算結果が正確に再現されます。累積和を計算していく過程で現れた値の最大値が、求める答えになります。この手法により、計算量をO(N + m)まで削減できます。

#include<iostream>
using namespace std;

int FindMaximum(int a, int b){
    if(a > b)
        return a;
    return b;
}

int findmax(int arr[], int N){
    int maxVal = 0;
    int sum = 0;
    for(int i = 0; i < N; i++){
        sum += arr[i];
        maxVal = FindMaximum(maxVal, sum);
    }
    return maxVal;
}

void updateVal(int arr[], int L, int R, int K){
    arr[L] += K;
    arr[R+1] -= K;
}

int main(){
    int N = 5;
    int arr[N + 1] = {0}; // R+1へのアクセスに備え、余分に1要素確保
    int M = 4;
    int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}};
    for(int i = 0; i < M; i++){
        updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]);
    }
    cout<<"The maximum value in the array after "<<M<<" range increment operations is "<<findmax(arr, N);
    return 0;
}

出力

The maximum value in the array after 4 range increment operations is 34

なお、R+1番目の位置へ書き込むため、配列はN+1個分確保しておくと安全です。これにより、区間の末尾が配列の最終要素だった場合でも範囲外アクセスを防げます。

まとめ

範囲加算のような「区間一括更新」の問題では、差分配列と累積和を組み合わせるテクニックが非常に有効です。競技プログラミングでも頻出の考え方なので、ぜひマスターしておきましょう。