数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序中更新给定索引和查找区间最大公约数的查询
在这个问题中，我们给定一个大小为 N 的数组 arr[] 和 Q 个查询，这些查询可以是两种类型。我们的任务是创建一个程序来解决这些查询，以更新给定索引并查找范围内的最大公约数。
查询为 -
类型 1 - {1, index, value} - 将给定索引处的元素增加 value。
类型 2 - {2, L, R} - 查找索引范围 [L, R] 内元素的最大公约数。
问题描述 - 我们需要找到范围 [L, R] 内的元素的最大公约数并返回该值。
让我们举个例子来理解这个问题，
输入
arr[] = {5, 1, 7, 3, 8}, Q = 3
Queries: {{2, 2 , 5}, {1, 3, 6}, {2, 2, 5}}输出
解释
解决方案方法
解决该问题的一种方法是使用线段树，线段树用于预处理数组的最大公约数。这将减少计算每个查询的最大公约数的时间。
创建和使用线段树
我们这里使用的线段树是一棵树，它将数组的元素存储为叶子节点，并将元素的最大公约数存储为内部节点。
程序说明我们解决方案的工作原理，
示例
#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
更新于: 2020-12-22
193 次浏览
广告