किसी दिए गए इंडेक्स को अपडेट करने और C++ प्रोग्राम में रेंज में gcd खोजने के लिए क्वेरी

इस समस्या में, हमें आकार N और Q प्रश्नों की एक सरणी गिरफ्तारी [] दी जाती है जो दो प्रकार की हो सकती है। हमारा काम किसी दिए गए इंडेक्स को अपडेट करने और रेंज में जीसीडी खोजने के लिए प्रश्नों को हल करने के लिए एक प्रोग्राम बनाना है।

प्रश्न हैं -

टाइप 1 − {1, इंडेक्स, वैल्यू} - दिए गए इंडेक्स पर एलिमेंट को वैल्यू के हिसाब से बढ़ाएं।

टाइप 2 - {2, एल, आर} - इंडेक्स रेंज [एल, आर] में तत्वों की जीसीडी खोजें।

समस्या का विवरण - हमें [L, R] श्रेणी में मौजूद तत्वों की GCD ढूंढनी होगी और मान वापस करना होगा।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

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

आउटपुट

स्पष्टीकरण

समाधान दृष्टिकोण

समस्या को हल करने का एक तरीका सेगमेंट ट्री का उपयोग करना है जिसका उपयोग जीसीडी को सरणियों के लिए प्रीप्रोसेस करने के लिए किया जाता है। इससे प्रत्येक क्वेरी के लिए 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