數組中給定索引范圍的 GCD · GeeksForGeeks 中文系列教程

# 數組中給定索引范圍的 GCD > 原文： [https://www.geeksforgeeks.org/gcds-of-a-given-index-ranges-in-an-array/](https://www.geeksforgeeks.org/gcds-of-a-given-index-ranges-in-an-array/) 給定一個數組`a[0 ... n-1]`。我們應該能夠有效地找到從索引`qs`（查詢開始）到`qe`（查詢結束）的 GCD，其中`0 <= qs <= qe <= n-1`。范例： ``` 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]`范圍內。現在可以以`O(1)`時間計算給定范圍的 GCD，但是預處理需要`O(n ^ 2)`時間。同樣，這種方法需要`O(n ^ 2)`額外的空間，這對于大型輸入數組可能會變得很大。 **方法 3（段樹）** 先決條件：[段樹系列 1](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/) ，[段樹系列 2](https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/) 段樹可用于在適當的時間內進行預處理和查詢。使用段樹，預處理時間為`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`。 * 段樹的高度將為`?log2(n)?`。由于樹是使用數組表示的，并且必須保持父索引和子索引之間的關系，因此分配給段樹的內存大小將為`2 * 2^?log2(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++ ```cpp // 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" << "\n"; ????????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) << "\n"; ????return 0; } ``` ## Java ```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# ```cs // 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(Log n * Log n)`。如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。