একটি প্রদত্ত সূচী আপডেট করতে এবং C++ এ পরিসরে gcd খুঁজে পেতে প্রশ্ন করুন

এই টিউটোরিয়ালে, আমরা একটি প্রদত্ত সূচক আপডেট করার জন্য এবং পরিসরে gcd খুঁজে বের করার জন্য প্রশ্নগুলি খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব৷

এর জন্য আমাদেরকে পূর্ণসংখ্যা এবং Q প্রশ্ন সম্বলিত একটি অ্যারে দেওয়া হবে। আমাদের কাজ হল প্রদত্ত প্রশ্নের ফলাফল খুঁজে বের করা (X দ্বারা একটি প্রদত্ত মান আপডেট করা, দুটি প্রদত্ত মানের মধ্যে gcd খুঁজে পাওয়া)।

উদাহরণ

#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