数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究在 C++ 中更新给定索引并查找范围内最大公约数的查询
在本教程中，我们将讨论一个程序以查找更新给定索引和查找范围内最大公约数的查询。
为此，我们将得到一个包含整数和 Q 个查询的数组。我们的任务是找到给定查询的结果（通过 X 更新给定值，找到两个给定值之间的最大公约数）。
示例
#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
更新于：19-Aug-2020
84 人看过
广告