查询以更新给定索引并在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

以上是 查询以更新给定索引并在C ++中找到范围内的gcd 的全部内容, 来源链接: utcz.com/z/317064.html

回到顶部