【C言語】複数の範囲加算クエリを処理して更新後の配列を出力する方法

本記事では、整数m個を含む配列arr[m]と、配列に加算する値nが与えられ、開始位置と終了位置を指定したr個のクエリを処理するCプログラムを紹介します。各クエリに対して、指定された開始インデックスから終了インデックスまでの範囲にあるすべての要素に値nを加算し、その結果を出力します。

実行例

入力:
arr[] = {1, 2, 3, 4, 5}
query[] = { { 0, 3 }, { 1, 2 } }
n = 2

出力:
Query1: { 3, 4, 5, 6, 5 }
Query2: { 3, 6, 7, 6, 5 }

この問題は、シンプルなアプローチで解決できます。手順は以下の通りです。

• すべてのクエリを順番に処理し、各クエリで指定された開始位置から終了位置まで配列を走査します。
• 走査した各要素に値nを加算し、その都度配列全体を出力します。

アルゴリズム

START
STEP 1 : 開始位置(start)と終了位置(end)を格納する構造体 range を宣言する
STEP 2 : 関数 add_tomatrix(int arr[], struct range r[], int n, int size, int m) 内で
    int i, j, k;
    FOR i = 0 AND i < m AND i++ のループ
        FOR j = r[i].start AND j<= r[i].end AND j++ のループ
            arr[j] = arr[j] + n
        END FOR
        FOR k = 0 AND k < size AND k++ のループ
            PRINT arr[k]
        END FOR
    END FOR
STOP

サンプルコード

#include <stdio.h>
struct range{
    int start, end; // 配列要素の範囲を指定するための構造体
};
int add_tomatrix(int arr[], struct range r[], int n, int size, int m){
    int i, j, k;
    for ( i = 0; i < m; i++) // 定義した構造体内のすべての要素を処理{
        for(j = r[i].start; j<= r[i].end; j++) // 更新したい範囲の開始から終了まで{
            arr[j] += n; // 指定された範囲の値を加算
        }
        printf("Query %d:", i+1);
        for ( k = 0; k < size; k++){
            printf(" %d",arr[k]); // 各クエリ処理後に配列全体を出力
        }
        printf("\n");
    }
}
int main(int argc, char const *argv[]){
    int arr[] ={3, 4, 8, 1, 10};
    struct range r[] = {{0,2}, {1, 3}, {3, 4}};
    int n = 2;
    int size = sizeof(arr)/sizeof(arr[0]);
    int m = sizeof(r)/sizeof(r[0]);
    add_tomatrix(arr, r, n, size, m);
    return 0;
}

実行結果

上記のプログラムを実行すると、以下の出力が生成されます。

Query 1: 5 6 10 1 10
Query 2: 5 8 12 3 10
Query 3: 5 8 12 5 12

処理の流れの解説

このプログラムでは、まず範囲(開始インデックスと終了インデックス)を保持するためのstruct rangeを定義しています。add_tomatrix関数は、クエリの数だけ外側のループを回し、その中で各クエリが示す範囲の要素に値nを加算します。範囲内の加算が完了したら、配列全体を走査して現在の状態を出力します。

例えば、最初のクエリ{0, 2}では、インデックス0から2までの要素(3, 4, 8)に2が加算され、{5, 6, 10, 1, 10}となります。次のクエリ{1, 3}では、この状態からさらにインデックス1から3までに2が加算され、{5, 8, 12, 3, 10}となります。このように、前のクエリの結果が次のクエリにも引き継がれる点に注意してください。

このアプローチの計算量は、クエリごとに最大O(size)の操作が必要となるため、全体でO(m × size)となります。クエリ数や配列サイズが非常に大きい場合は、差分配列(Difference Array)やセグメント木などのより効率的な手法を検討するとよいでしょう。