इस ट्यूटोरियल में, हम किसी दिए गए इंडेक्स को अपडेट करने और रेंज में gcd खोजने के लिए क्वेरी खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें पूर्णांकों और Q प्रश्नों वाली एक सरणी प्रदान की जाएगी। हमारा काम दिए गए प्रश्नों का परिणाम खोजना है (एक्स द्वारा दिए गए मान को अपडेट करना, दो दिए गए मानों के बीच जीसीडी ढूंढना)।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
//getting middle index
int findMiddle(int s, int e) {
return (s + (e - s) / 2);
}
//updating values at given indices
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);
}
}
//finding gcd values in the given range
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