Java 在数组中找到给定索引范围的最大公约数

在数据结构领域，范围查询是一种预处理方法，可以以高效的方式操作一些输入数据。范围查询负责回答对特定输入的任何查询，并在任何数据子集上执行。如果我们想要从表中复制一些数据列，我们需要维护该特定数据集的索引。索引是一个直接的链接或密钥，旨在在数据集中提供高效的搜索过程。它主要用于加快从遗失的数据源中检索数据的过程。

在数学中，最大公约数（GCD）是一个最大可能的整数，可以整除输入的两个整数。在这里，所有数字必须具有非零值。只需举一个示例−

GCD of 70, 80 = 10 (10 is the largest number which divides them with remainder as 0)
GCD of 42, 120, 285 = 3 (3 is the largest number which divides them with remainder as 0)

在数组中找出给定索引范围内的最大公约数的算法（详细版）

步骤1-开始
步骤2-构建arr[0]到arr[n-1]的部分
步骤3-继续等分
步骤4-对这两部分进行递归调用
步骤5-对于每个部分，只保存最大公约数值将保存在一个段树中
步骤6-构建另一个段树，从底部填充
步骤7-每个节点存储某个范围内的GCD数据
步骤8-如果节点范围是startQuery和endQuery，则返回一个值节点
步骤9-否则，如果范围无效，则返回null或-1作为输出
步骤10-否则，返回一个作为递归调用的GCD函数
步骤11-结束

在数组中找出给定索引范围内的最大公约数的算法（简短版）

步骤1-假设a和b是两个非零整数
步骤2-令a mod b = R
步骤3-如果a=b且b=R
步骤4-然后重复步骤2和步骤3
步骤5-过程将一直运行，直到a mod b大于零
步骤6-GCD = b
步骤7-结束

在数组中找出给定索引范围内的最大公约数的语法

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(QNlog(Ai))，辅助空间评估为O(1)。

方法

方法 – 使用段树在给定范围内找到一个数字的最大公约数的程序

使用段树在给定范围内找到一个数字的最大公约数的程序

要使用段树在给定范围内找到一个数字的最大公约数，我们需要遵循一些不可避免的步骤。

构建段树
- 输入数组的元素是叶节点。
- 每个单个的内部节点表示所有叶节点的最大公约数。
- 数组表示可以由段树实现。

-2*(i+1)，索引的左元素

-2*(i+2)，索引的右元素

-父节点是floor((i-1)/2)

使用给定的数组构建新的段树：
- 从段arr[0 . . . n-1]开始进行过程。
- 将它们分为两半。
- 对两半进行相同的调用。
- 存储最大公约数的值。
构建给定范围的最大公约数：
- 对于每一个可能的查询，将树的两半移动到左边和右边。
- 当给定范围与一半重叠时，返回该节点。
- 当它在给定范围之外时，在那一刻返回0。
- 对于部分重叠，遍历并根据以下的方法返回。

示例

import java.io.*;
public class tutorialspointGCD{
   private static int[] segTree;
   public static int[] buildSegmentTree(int[] arr){
      int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
      int size = 2*(int)Math.pow(2, height)-1;
      segTree = new int[size];
      SegementTree(arr, 0, arr.length-1, 0);
      return segTree;
   }
   public static int SegementTree(int[] arr, int startNode,int endNode, int si){
        if (startNode==endNode) {
            segTree[si] = arr[startNode];
            return segTree[si];
         }
         int mid = startNode+(endNode-startNode)/2;
        segTree[si] = gcd(SegementTree(arr, startNode, mid, si*2+1),
                          SegementTree(arr, mid+1, endNode, si*2+2));
        return segTree[si];
   }
   private static int gcd(int a, int b){
      if (a < b){
            int temp = b;
            b = a;
            a = temp;
         }
         if (b==0)
            return a;
        return gcd(b,a%b);
   }
   public static int findRangeGcd(int startNode, int endNode, int[] arr){
      int n = arr.length;
      if (startNode<0 || endNode > n-1 || startNode>endNode)
         throw new IllegalArgumentException("Invalid arguments");
      return findGcd(0, n-1, startNode, endNode, 0);
   }
   public static int findGcd(int startNode, int endNode, int startQuery, int endQuery, int si){
      if (startNode>endQuery || endNode < startQuery)
            return 0;
      if (startQuery<=startNode && endQuery>=endNode)
            return segTree[si];
      int mid = startNode+(endNode-startNode)/2;
      return gcd(findGcd(startNode, mid, startQuery, endQuery, si*2+1),
                   findGcd(mid+1, endNode, startQuery, endQuery, si*2+2));
   }
   public static void main(String[] args)throws IOException{
      int[] a = {10, 5, 18, 9, 24};
      buildSegmentTree(a);
      int l = 0, r = 1;
      System.out.println("Greatest Common Divisor is here. Please collect the data: "+findRangeGcd(l, r, a));
      l = 2;
      r = 4;
      System.out.println("Greatest Common Divisor is here. Please collect the data: "+findRangeGcd(l, r, a));
      l = 0;
      r = 3;
      System.out.println("Greatest Common Divisor is here s . Please collect the data: "+findRangeGcd(l, r, a));
   }
}

输出

Greatest Common Divisor is here. Please collect the data: 5
Greatest Common Divisor is here. Please collect the data: 3
Greatest Common Divisor is here s . Please collect the data: 1