给定一个数组a[0…n-1]。我们应该能够有效地找到从索引qs（查询开始）到qe（查询结束）的GCD，其中0<=qs<=qe<=n-1。
null
例子：
Input : a[] = {2, 3, 60, 90, 50};
Index Ranges : {1, 3}, {2, 4}, {0, 2}
Output: GCDs of given ranges are 3, 10, 1
方法1（简单）
一个简单的解决方案是运行从qs到qe的循环，并在给定范围内找到GCD。在最坏的情况下，这个解决方案需要O（n）时间。
方法2（二维阵列）
另一个解决方案是创建一个2D数组，其中条目[i，j]将GCD存储在范围arr[i..j]中。给定范围的GCD现在可以在O（1）时间内计算，但预处理需要O（n^2）时间。此外，这种方法需要O（n^2）额外的空间，这对于大型输入阵列来说可能会变得巨大。
方法3（分段树）
先决条件： 段树集1 , 段树集2 分段树可以在适当的时间内进行预处理和查询。对于段树，预处理时间为O（n），GCD查询的时间为O（Logn）。存储段树所需的额外空间为O（n）。
分段树的表示
- 叶节点是输入数组的元素。
- 每个内部节点代表其下所有叶片的GCD。
树的数组表示用于表示段树，即索引i处的每个节点，
- 左边的孩子在索引2*i+1处
- 右边的孩子在2*i+2，父母在楼层（（i-1）/2）。
从给定数组构造段树
- 从一段arr[0…n-1]开始，继续分成两半。每次我们将当前段分成两半（如果它尚未成为长度为1的段），然后在两半上调用相同的过程，对于每个这样的段，我们将GCD值存储在段树节点中。
- 除最后一层外，构建的段树的所有层都将完全填充。此外，树将是一个完整的二叉树（每个节点有0或两个子节点），因为我们总是在每个级别将段分成两半。
- 由于构造的树总是具有n个叶子的完整二叉树，因此将有n-1个内部节点。因此，节点总数将为2*n–1。
- 分段树的高度将为&lceillog 2. n&rceil。由于树是使用数组表示的，并且必须保持父索引和子索引之间的关系，所以为段树分配的内存大小将为2*2 ⌈日志 2. N⌉ – 1
查询给定范围的GCD
/ qs --> query start index, qe --> query end index
int GCD(node, qs, qe)
{
if range of node is within qs and qe
return value in node
else if range of node is completely
outside qs and qe
return INFINITE
else
return GCD( GCD(node's left child, qs, qe),
GCD(node's right child, qs, qe) )
}
下面是这个方法的实现。
C++
// C++ Program to find GCD of a number in a given Range // using segment Trees #include <bits/stdc++.h> using namespace std; // To store segment tree int *st; /* A recursive function to get gcd of given range of array indexes. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[index] qs & qe --> Starting and ending indexes of query range */ 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)); } //Finding The gcd of given Range int findRangeGcd( int ss, int se, int arr[], int n) { if (ss<0 || se > n-1 || ss>se) { cout << "Invalid Arguments" << "" ; return -1; } return findGcd(0, n-1, ss, se, 0); } // A recursive function that constructs Segment Tree for // array[ss..se]. si is index of current node in segment // tree st 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]; } /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ 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; } // Driver program to test above functions int main() { int a[] = {2, 3, 6, 9, 5}; int n = sizeof (a)/ sizeof (a[0]); // Build segment tree from given array constructSegmentTree(a, n); // Starting index of range. These indexes are 0 based. int l = 1; // Last index of range.These indexes are 0 based. int r = 3; cout << "GCD of the given range is:" ; cout << findRangeGcd(l, r, a, n) << "" ; return 0; } |
JAVA
// Java Program to find GCD of a number in a given Range // using segment Trees import java.io.*; public class Main { private static int [] st; // Array to store segment tree /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ public static int [] constructSegmentTree( int [] arr) { int height = ( int )Math.ceil(Math.log(arr.length)/Math.log( 2 )); int size = 2 *( int )Math.pow( 2 , height)- 1 ; st = new int [size]; constructST(arr, 0 , arr.length- 1 , 0 ); return st; } // A recursive function that constructs Segment // Tree for array[ss..se]. si is index of current // node in segment tree st public static 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]; } // Function to find gcd of 2 numbers. private static int gcd( int a, int b) { if (a < b) { // If b greater than a swap a and b int temp = b; b = a; a = temp; } if (b== 0 ) return a; return gcd(b,a%b); } //Finding The gcd of given Range public static int findRangeGcd( int ss, int se, int [] arr) { int n = arr.length; if (ss< 0 || se > n- 1 || ss>se) throw new IllegalArgumentException( "Invalid arguments" ); return findGcd( 0 , n- 1 , ss, se, 0 ); } /* A recursive function to get gcd of given range of array indexes. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[si] qs & qe --> Starting and ending indexes of query range */ public static 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 )); } // Driver Code public static void main(String[] args) throws IOException { int [] a = { 2 , 3 , 6 , 9 , 5 }; constructSegmentTree(a); int l = 1 ; // Starting index of range. int r = 3 ; //Last index of range. System.out.print( "GCD of the given range is: " ); System.out.print(findRangeGcd(l, r, a)); } } |
C#
// C# Program to find GCD of a number in a given Range // using segment Trees using System; class GFG { private static int [] st; // Array to store segment tree /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ public static int [] constructSegmentTree( int [] arr) { int height = ( int )Math.Ceiling(Math.Log(arr.Length)/Math.Log(2)); int size = 2*( int )Math.Pow(2, height) - 1; st = new int [size]; constructST(arr, 0, arr.Length - 1, 0); return st; } // A recursive function that constructs Segment // Tree for array[ss..se]. si is index of current // node in segment tree st public static 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]; } // Function to find gcd of 2 numbers. private static int gcd( int a, int b) { if (a < b) { // If b greater than a swap a and b int temp = b; b = a; a = temp; } if (b == 0) return a; return gcd(b,a % b); } // Finding The gcd of given Range public static int findRangeGcd( int ss, int se, int [] arr) { int n = arr.Length; if (ss < 0 || se > n-1 || ss > se) { Console.WriteLine( "Invalid arguments" ); return int .MinValue; } return findGcd(0, n - 1, ss, se, 0); } /* A recursive function to get gcd of given range of array indexes. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[si] qs & qe --> Starting and ending indexes of query range */ public static 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)); } // Driver Code public static void Main(String[] args) { int [] a = {2, 3, 6, 9, 5}; constructSegmentTree(a); int l = 1; // Starting index of range. int r = 3; //Last index of range. Console.Write( "GCD of the given range is: " ); Console.Write(findRangeGcd(l, r, a)); } } // This code has been contributed by 29AjayKumar |
输出：
GCD of the given range is: 3
时间复杂性： 树构造的时间复杂度为O（n*log（min（a，b）），其中n是模式数，a和b是在合并操作期间计算GCD的节点。共有2n-1个节点，每个节点的值在树构造中只计算一次。查询的时间复杂度为O（logn*logn）。
本文由 尼希尔·特克瓦尼 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
