इस ट्यूटोरियल में, हम दिए गए इंडेक्स को अपडेट करने और रेंज में GCD खोजने के लिए क्वेरीज खोजने के प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें एक ऐरे दिया जाएगा जिसमें पूर्णांक होंगे और Q क्वेरीज होंगी। हमारा कार्य दी गई क्वेरीज का परिणाम खोजना है (दिए गए मान को X से अपडेट करना, दो दिए गए मानों के बीच GCD खोजना)।
उदाहरण
#include <bits/stdc++.h> using namespace std; //मध्य इंडेक्स प्राप्त करना int findMiddle(int s, int e) { return (s + (e - s) / 2); } //दिए गए इंडेक्स पर मान अपडेट करना void updateIndexValue(int* st, int ss, int se, int i, int diff, int si) { if (i < ss || i > se) return; st[si] = st[si] + diff; if (se != ss) { int mid = findMiddle(ss, se); updateIndexValue(st, ss, mid, i, diff, 2 * si + 1); updateIndexValue(st, mid + 1, se, i, diff, 2 * si + 2); } } //दिए गए रेंज में GCD मान खोजना int findGCDRange(int* st, int ss, int se, int qs, int qe, int si) { if (qs <= ss && qe >= se) return st[si]; if (se < qs || ss > qe) return 0; int mid = findMiddle(ss, se); return __gcd(findGCDRange(st, ss, mid, qs, qe, 2 * si + 1), findGCDRange(st, mid + 1, se, qs, qe, 2 * si + 2)); } int findingGCD(int* st, int n, int qs, int qe) { if (qs < 0 || qe > n - 1 || qs > qe) { cout << "Not valid input"; return -1; } return findGCDRange(st, 0, n - 1, qs, qe, 0); } void updatingAllValues(int arr[], int* st, int n, int i, int new_val) { if (i < 0 || i > n - 1) { cout << "Not valid input"; return; } int diff = new_val - arr[i]; arr[i] = new_val; updateIndexValue(st, 0, n - 1, i, diff, 0); } int calcGCDIndex(int arr[], int ss, int se, int* st, int si) { if (ss == se) { st[si] = arr[ss]; return arr[ss]; } int mid = findMiddle(ss, se); st[si] = __gcd(calcGCDIndex(arr, ss, mid, st, si * 2 +1), calcGCDIndex(arr, mid + 1, se, st, si * 2 + 2)); return st[si]; } int* calculatingGCD(int arr[], int n) { int x = (int)(ceil(log2(n))); int max_size = 2 * (int)pow(2, x) - 1; int* st = new int[max_size]; calcGCDIndex(arr, 0, n - 1, st, 0); return st; } int main() { int arr[] = { 2, 5, 16, 7, 9, 23 }; int n = sizeof(arr) / sizeof(arr[0]); int* st = calculatingGCD(arr, n); cout << findingGCD(st, n, 2, 5) << endl; return 0; } आउटपुट
1