C++で範囲合計クエリ後の配列から元の初期配列を復元する方法

問題の概要

この問題では、サイズNの配列res[]が与えられ、範囲合計クエリ（レンジサムクエリ）を実行した後の配列から、元の初期配列を求めることが課題となります。

具体的には、ある初期配列に対して[s, e, val]という形式のクエリを実行した結果、与えられた配列rel[]が得られるような、クエリ実行前の元の配列を見つける必要があります。

各[s, e, val]クエリの各要素は、以下の意味を持ちます。

• s → 開始インデックス
• e → 終了インデックス
• val → 配列のs番目からe番目までの各要素に加算する更新値

具体例で問題を理解しよう

入力：rel[] = {7, 4, 8}
Query[][] = {{1, 2, 1},
{0, 1, 3}}
出力：{4, 0, 7}

説明：

initialArray = {4, 0, 7}; query = {1, 2, 1}; finalArray = {4, 1, 8}
initialArray = {4, 1, 8}; query = {0, 1, 3}; finalArray = {7, 4, 8}

このように、初期配列{4, 0, 7}に対してクエリを順番に適用していくと、最終的に与えられた配列{7, 4, 8}が得られることが確認できます。

解法アプローチ

この問題のシンプルな解法は、すべてのクエリを逆の操作で処理するというものです。通常、クエリ[s, e, val]は配列のs番目からe番目までの要素にvalを加算しますが、初期配列を復元する場合は、この操作を逆向きに行い、与えられた配列の該当範囲からvalを減算していきます。

すべてのクエリをこの方法で処理し終えたときに残る配列が、求める初期配列となります。この手法の計算量は、クエリ数をQ、配列サイズをNとすると、最悪の場合O(Q×N)となります。

実装例

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

#include <iostream>
using namespace std;
void calcInitialArrayQueries(int arr[], int n, int query[][3], int q) {
    for (int i = 0; i < q; i++) {
        for (int j = query[i][0]; j <= query[i][1]; j++) {
            arr[j] = arr[j] - query[i][2];
        }
    }
    for (int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
}
int main() {
    int arr[] = { 5, 1, 8, 2, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int query[][3] = { {0, 2, -2}, {1, 4, 3}};
    int q = sizeof(query) / sizeof(query[0]);
    cout<<"Initial array : "; calcInitialArrayQueries(arr, n, query, q);
    return 0;
}

出力結果

Initial array : 7 0 7 -1 6

このプログラムでは、配列{5, 1, 8, 2, 9}に対して2つのクエリ{0, 2, -2}と{1, 4, 3}を逆順に適用（減算）することで、クエリ実行前の初期配列{7, 0, 7, -1, 6}を正しく復元できています。