指定されたインデックスを更新し、C++プログラムで範囲内のgcdを見つけるためのクエリ

この問題では、サイズNおよびQクエリの配列arr []が与えられます。これは、2つのタイプになります。私たちのタスクは、クエリを解決して特定のインデックスを更新し、範囲内のGCDを見つけるプログラムを作成することです。

クエリは-

タイプ1 − {1、index、value}-指定されたインデックスの要素を値だけ増やします。

タイプ2 − {2、L、R}-インデックス範囲[L、R]の要素のGCDを見つけます。

問題の説明 − [L、R]の範囲にある要素のGCDを見つけて、値を返す必要があります。

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

入力

arr[] = {5, 1, 7, 3, 8}, Q = 3
Queries: {{2, 2 , 5}, {1, 3, 6}, {2, 2, 5}}

出力

説明

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

この問題を解決するためのアプローチは、アレイのGCDを前処理するために使用されるセグメントツリーを使用することです。これにより、各クエリのGCDを計算する時間が短縮されます。

セグメントツリーの作成と操作

ここで使用しているセグメントツリーは、配列の要素をリーフノードとして格納し、要素のGCDを内部ノードとして格納するツリーです。

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

例

#include <bits/stdc++.h>
using namespace std;
int calcGcdRangeRec(int* st, int segL, int segR, int L, int R, int currNode) {
   if (L <= segL && R >= segR)
      return st[currNode];
   if (segR < L || segL > R)
      return 0;
   int mid = (segL + (segR - segL)/2);
   int GcdL = calcGcdRangeRec(st, segL, mid, L, R, 2 * currNode + 1) ;
   int GcdR = calcGcdRangeRec(st, mid + 1, segR, L, R, 2 * currNode + 2);
   return __gcd(GcdL, GcdR);
}
void updateArrayValueRec(int* st, int L, int R, int index, int diff, int currNode) {
   if (index < L || index > R)
      return;
   st[currNode] = st[currNode] + diff;
   if (R != L) {
      int mid = (L + (R - L)/ 2);
      updateArrayValueRec(st, L, mid, index, diff, 2 * currNode + 1);
      updateArrayValueRec(st, mid + 1, R, index, diff, 2 * currNode + 2);
   }
}
void updateArrayValue(int arr[], int* st, int n, int index, int newVal) {
   if (index < 0 || index > n - 1)
      cout << "Invalid Input";
   else{
      int diff = newVal - arr[index];
      arr[index] = newVal;
      updateArrayValueRec(st, 0, n - 1, index, diff, 0);
   }
}
int calcGcdRange(int* st, int n, int L, int R) {
   if (L < 0 || R > n - 1 || L > R) {
      cout << "Invalid Input";
      return -1;
   }
   return calcGcdRangeRec(st, 0, n - 1, L, R, 0);
}
int constructGcdST(int arr[], int L, int R, int* st, int currNode) {
   if (L == R) {
      st[currNode] = arr[L];
      return arr[L];
   }
   int mid = (L + (R - L)/2);
   int GcdL = constructGcdST(arr, L, mid, st, currNode * 2 + 1);
   int GcdR = constructGcdST(arr, mid + 1, R, st, currNode * 2 + 2);
   st[currNode] = __gcd(GcdL, GcdR);
   return st[currNode];
}
int main() {
   int arr[] = { 1, 3, 6, 9, 9, 11 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int Q = 3;
   int query[3][3] = {{2, 1, 3}, {1, 1 , 10}, {2, 1, 3}};
   int value = (int)(ceil(log2(n)));
   int size = 2 * (int)pow(2, value) - 1;
   int* st = new int[size];
   constructGcdST(arr, 0, n - 1, st, 0);
   for(int i = 0; i < n; i++){
      if(query[i][0] == 1){
         cout<<"Query "<<(i + 1)<<": Updating Values!\n";
         updateArrayValue(arr, st, n, query[i][1], query[i][2]);
      }
      if(query[i][0] == 2)
      cout<<"Query "<<(i + 1)<<": GCD is "<<calcGcdRange(st, n, query[i][1], query[i][2])<<endl;
   }
   return 0;
}

入力

Query 1: GCD is 3
Query 2: Updating Values!
Query 3: GCD is 1