查询以更新给定索引并在C ++程序的范围内找到gcd

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，我们为数组arr []设置了大小为N和Q的查询，可以是两种类型。我们的任务是创建一个程序来解决查询以更新给定索引并找到该范围内的GCD。

查询是-

类型1- {1，索引，值}-按值增加给定索引处的元素。

类型2- {2，L，R}-查找索引范围为[L，R]的元素的GCD。

问题描述-我们需要找到[L，R]范围内元素的GCD并返回值。

让我们举个例子来了解这个问题，

输入值

arr[] = {5, 1, 7, 3, 8}, Q = 3
Queries: {{2, 2 , 5}, {1, 3, 6}, {2, 2, 5}}
输出结果

说明

解决方法

解决该问题的一种方法是使用段树，该段树用于预处理数组的GCD。这将减少为每个查询计算GCD的时间。

创建和使用细分树

我们在这里使用的段树是一棵将数组元素存储为叶节点，将元素的GCD存储为内部节点的树。

该程序说明了我们解决方案的工作原理，

示例

#include <bits/stdc++.h>
using namespace std;
int calcGcdRangeRec(int* st, int segL, int segR, int L, int R, int currNode) {
   if (L <= segL && R >= segR)
      return st[currNode];
   if (segR < L || segL > R)
      return 0;
   int mid = (segL + (segR - segL)/2);
   int GcdL = calcGcdRangeRec(st, segL, mid, L, R, 2 * currNode + 1) ;
   int GcdR = calcGcdRangeRec(st, mid + 1, segR, L, R, 2 * currNode + 2);
   return __gcd(GcdL, GcdR);
}
void updateArrayValueRec(int* st, int L, int R, int index, int diff, int currNode) {
   if (index < L || index > R)
      return;
   st[currNode] = st[currNode] + diff;
   if (R != L) {
      int mid = (L + (R - L)/ 2);
      updateArrayValueRec(st, L, mid, index, diff, 2 * currNode + 1);
      updateArrayValueRec(st, mid + 1, R, index, diff, 2 * currNode + 2);
   }
}
void updateArrayValue(int arr[], int* st, int n, int index, int newVal) {
   if (index < 0 || index > n - 1)
      cout << "Invalid Input";
   else{
      int diff = newVal - arr[index];
      arr[index] = newVal;
      updateArrayValueRec(st, 0, n - 1, index, diff, 0);
   }
}
int calcGcdRange(int* st, int n, int L, int R) {
   if (L < 0 || R > n - 1 || L > R) {
      cout << "Invalid Input";
      return -1;
   }
   return calcGcdRangeRec(st, 0, n - 1, L, R, 0);
}
int constructGcdST(int arr[], int L, int R, int* st, int currNode) {
   if (L == R) {
      st[currNode] = arr[L];
      return arr[L];
   }
   int mid = (L + (R - L)/2);
   int GcdL = constructGcdST(arr, L, mid, st, currNode * 2 + 1);
   int GcdR = constructGcdST(arr, mid + 1, R, st, currNode * 2 + 2);
   st[currNode] = __gcd(GcdL, GcdR);
   return st[currNode];
}
int main() {
   int arr[] = { 1, 3, 6, 9, 9, 11 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int Q = 3;
   int query[3][3] = {{2, 1, 3}, {1, 1 , 10}, {2, 1, 3}};
   int value = (int)(ceil(log2(n)));
   int size = 2 * (int)pow(2, value) - 1;
   int* st = new int[size];
   constructGcdST(arr, 0, n - 1, st, 0);
   for(int i = 0; i < n; i++){
      if(query[i][0] == 1){
         cout<<"Query "<<(i + 1)<<": Updating Values!\n";
         updateArrayValue(arr, st, n, query[i][1], query[i][2]);
      }
      if(query[i][0] == 2)
      cout<<"Query "<<(i + 1)<<": GCD is "<<calcGcdRange(st, n, query[i][1], query[i][2])<<endl;
   }
   return 0;
}

输入值

Query 1: GCD is 3
Query 2: Updating Values!
Query 3: GCD is 1

以上是 查询以更新给定索引并在C ++程序的范围内找到gcd 的全部内容， 来源链接： utcz.com/z/315928.html

回到顶部