C ++で範囲合計クエリを実行した後、指定された配列から初期配列を検索します

この問題では、サイズNの配列res []が与えられます。私たちのタスクは、範囲合計クエリの後に、指定された配列から初期配列を検索することです。

[s、e、val]クエリを実行すると配列rel[]を返す開始配列を見つける必要があります。

各[s、e、val]クエリは次のように解決されます

s->開始インデックス

e->終了インデックス

val->配列内のsからeまでの各要素に追加される値を更新します。

問題を理解するために例を見てみましょう

Input : rel[] = {7, 4, 8}
Query[][] = {{1, 2, 1},
{0, 1, 3}}
Output : {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}

ソリューションアプローチ

この問題の簡単な解決策は、すべてのクエリをトラバースすることです。すべてのクエリは、解決方法を使用して解決し、最後に見つかった配列を返します。ここで、initialArrayを見つけるには、逆の方法で操作する必要があります。つまり、指定された配列から減算します。

例

ソリューションの動作を説明するプログラム

#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