C++程序在数组中查找给定索引范围内的最大公约数

给定数组 a [0.。n-1]。我们应该能够有效地找到从索引 qs（查询开始）到 qe（查询结束）的GCD，其中0 <= qs <= qe <= n-1。例如：

输入：a [] = {2，3，60，90，50};
        索引范围：{1, 3}，{2, 4}，{0, 2}
输出：给定范围的GCD为3,10,1

方法1（简单）

一种简单的解决方案是从qs到qe运行循环，并在给定范围内找到GCD。在最坏的情况下，此解决方案需要O（n）时间。

方法2（2D数组）

另一种解决方案是创建一个2D数组，其中条目 [i，j] 存储范围 arr [i .. j] 中的GCD。现在可以在O（1）时间内计算给定范围的GCD，但是预处理需要O（n ^ 2）时间。而且，此方法需要O（n ^ 2）额外空间，对于大型输入数组而言可能会变得很大。

方法3（段树）

前提条件：段树集1，段树集2

段树可用于在适度的时间内进行预处理和查询。使用段树，预处理时间为O（n），GCD查询时间为O（Logn）。所需的额外空间是O（n），用于存储段树。

段树的表示

叶节点是输入数组的元素。
每个内部节点表示其下所有叶子的GCD。

使用树的数组表示用于表示段树，即对于索引为i的每个节点，

左子节点在索引2 * i + 1处
右子节点在2 * i + 2处，父节点在floor（（i-1）/ 2）处。

从给定数组构建段树

以段arr [0..n-1]开始，保持分成两半。每次我们将当前段分成两半（如果它尚未成为长度为1的段），则在两半的每个段上调用相同的过程，并且对于每个这样的段，我们在一个段树节点中存储GCD值。
构造的段树的所有级别都将完全填充，除了最后一级。此外，树将是一个完整的二叉树（每个节点具有0或两个子节点），因为我们总是在每个级别将段分成两半。
由于构建的树始终是具有n个叶子的完全二叉树，因此将有n-1个内部节点。因此，总节点数将为2 * n-1。
段树的高度将是&lceillog; 2 n⌉。由于使用数组表示树，并且必须维护父节点和子节点索引之间的关系，因此分配给段树的内存大小将是2 * 2 ⌈log 2 n⌉ – 1

在给定范围内查询GCD

/qs->查询起始索引，qe->查询结束索引
int GCD(node，qs，qe)
{
   如果节点范围位于QS和QE之间
则返回节点中的值
   否则，如果节点范围完全
QS和QE之外
返回无限制
   else
      返回GCD（GCD（节点的左子项、QS、QE），GCD（节点的右子项、QS、QE））
}

下面是该方法的实现：

// C++程序，用于在给定范围内找到数字的GCD
//使用分段树
#include 
using namespace std;

//存储分段树
int *st;

/*递归函数，用于获取给定范围数组索引的GCD
以下是此函数的参数。

st —>指向段树的指针
si —>段树中当前节点的索引。最初，0作为根始终传递为索引0
ss和se—>由当前节点表示的段的起始和结束索引，即st[index]
qs和qe—>查询范围的起始和结束索引*/
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));
}

//找到给定范围的GCD
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);
}

//递归构造段树的函数
//构造集合树 [ss..se]。Si是segment 中当前节点的索引 
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];
}

/*从给定值构造线段树的函数
此函数为线段树分配内存，并调用constructSTUtil()以填充分配的内存*/
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[] = {2, 3, 6, 9, 5};
int n = sizeof(a)/sizeof(a[0]);

//从给定数组构建线段树
constructSegmentTree(a, n);

//范围的起始索引。这些索引是基于0的。
int l = 1;

//范围的最后一个索引。这些索引是基于0的。
int r = 3;
cout << "给定范围的GCD是：";
cout << findRangeGcd(l, r, a, n) << "\n";

return 0;
}

输出: