Truy vấn để cập nhật một chỉ mục nhất định và tìm gcd trong phạm vi trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình tìm các truy vấn để cập nhật một chỉ mục nhất định và tìm gcd trong phạm vi.

Đối với điều này, chúng tôi sẽ được cung cấp một mảng chứa các số nguyên và truy vấn Q. Nhiệm vụ của chúng tôi là tìm kết quả của các truy vấn đã cho (cập nhật một giá trị nhất định cho X, tìm gcd giữa hai giá trị đã cho).

Ví dụ

#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;
}

Đầu ra

1