C++ 程序用于查找数组中给定索引范围的 GCD
在数据结构领域，范围查询是一种预处理方法，用于高效地对某些输入数据进行操作。范围查询负责回答任何数据子集上特定输入的任何查询。如果我们想从表中复制一些数据列，我们需要为该特定数据集维护一个索引。索引是直接链接或键，旨在提供数据集中的高效搜索过程。它主要用于加快从丢失的数据源中检索数据的速度。
在数学中，最大公约数又名 GCD 是一个最大的可能整数，它可以整除作为输入的两个整数。这里，所有数字都必须具有非零值。举个例子:
70, 80 的 GCD = 10(10 是能整除它们的最大数，余数为 0) 42, 120, 285 的 GCD = 3(3 是能整除它们的最大数，余数为 0)
在数组中查找给定索引范围的 GCD 的算法(详见)
步骤 1 − 开始
步骤 2 − 构造 arr[0] 到 arr[n-1] 的部分
步骤 3 − 继续相等划分
步骤 4 − 递归调用这两个部分
步骤 5 − 对于每个部分，只保存最大公约数值线段树
步骤 6 − 构建另一个线段树，从下到上填充它
步骤 7 − 每个节点存储具有一定范围的 GCD 的一些数据
步骤 8 − 如果节点范围是 startQuery 和 endQuery，则返回一个值节点
步骤 9 − 否则，如果范围无效，它将返回 null 或 -1 作为输出
步骤 10 − 否则，返回 GCD 函数作为递归调用
步骤 11 − 终止
在数组中查找给定索引范围的 GCD 的算法(简而言之)
步骤 1 − 假设 a 和 b 是两个非零值整数
步骤 2 - 设 a mod b = R
步骤 3 - 如果 a=b 且 b=R
步骤 4 - 然后，重复步骤 2 和步骤 3
步骤 5 - 进程将运行，直到 a mod b 大于零
步骤 6 - GCD = b
步骤 7 - 终止
用于在数组中查找给定索引范围的 GCD 的语法
Begin
if c = 0 OR d = 0, then
return 0
if c = d, then
return b
if c > d, then
return findGCD(c-d, d)
else
return findGCD(c, d-c)
End
在此语法中我们可以看到可能的逻辑代码，如何找到两个非零数字的最大公约数。该过程的时间复杂度为 O(Q*N*log(Ai))，辅助空间的评估为 O(1)。
要遵循的方法:-
方法 1 - 使用线段树在给定范围内查找数字的 GCD 的程序
使用线段树在给定范围内查找数字的 GCD 的程序
要使用线段树在给定范围内查找数字的 GCD，我们需要遵循一些不可避免的步骤。
线段树的构造:
输入数组的元素是叶节点。
每个单独的内部节点代表所有叶节点的 GCD。
数组表示可以通过线段来完成树。
-2*(i+1)，索引的左元素
-2*(i+2)，索引的右元素
-Parent 为 floor((i-1)/2)
使用给定数组构造新的线段树:
以线段 arr[0 . . . ] 开始该过程。 n-1]。
将它们分成两半。
对两半调用相同的方法。
存储 GCD 的值。
为 GCD 构建给定范围:
对于每个可能的查询，将存在的树的两半向左和向右移动。
当给定范围与一半重叠时；返回节点。
当它位于给定范围之外时，立即返回 0。
对于部分重叠，遍历并按照以下方法获取返回值。
示例
#include <bits/stdc++.h>
using namespace std;
int* st;
int findGcd(int ss, int se, int qs, int qe, int si) {
if (ss > qe || se < qs)
return 0;
if (qs <= ss && qe >= se)
return st[si];
int mid = ss + (se - ss) / 2;
return __gcd(findGcd(ss, mid, qs, qe, si * 2 + 1),
findGcd(mid + 1, se, qs, qe, si * 2 + 2));
}
int findRangeGcd(int ss, int se, int arr[], int n) {
if (ss < 0 || se > n - 1 || ss > se) {
cout << "Invalid Arguments"
<< "\n";
return -1;
}
return findGcd(0, n - 1, ss, se, 0);
}
int constructST(int arr[], int ss, int se, int si) {
if (ss == se) {
st[si] = arr[ss];
return st[si];
}
int mid = ss + (se - ss) / 2;
st[si]
= __gcd(constructST(arr, ss, mid, si * 2 + 1),
constructST(arr, mid + 1, se, si * 2 + 2));
return st[si];
}
int* constructSegmentTree(int arr[], int n) {
int height = (int)(ceil(log2(n)));
int size = 2 * (int)pow(2, height) - 1;
st = new int[size];
constructST(arr, 0, n - 1, 0);
return st;
}
int main() {
int a[] = { 20, 30, 60, 90, 50 };
int n = sizeof(a) / sizeof(a[0]);
constrainSegmentTree(a, n);
int l = 1;
int r = 3;
cout << "给定范围的 GCD 在这里。请收集您的数据:";
cout << findRangeGcd(l, r, a, n) << "\n";
return 0;
}
输出
给定范围的 GCD 在这里。请收集您的数据:30
结论
因此，在本文中，我们使用特定的编程环境开发了一些可能的代码。通过这些编码逻辑和提到的算法，我们已经学会了如何正确找出数组中给定索引范围的 GCD。
