Programa C++ para encontrar los GCD de rangos de índice dados en una array

Dada una array a[0 . . . n-1]. Deberíamos poder encontrar eficientemente el GCD desde el índice qs (inicio de consulta) hasta qe (final de consulta) donde 0 <= qs <= qe <= n-1. Ejemplo :

Input : a[] = {2, 3, 60, 90, 50};
        Index Ranges : {1, 3}, {2, 4}, {0, 2}
Output: GCDs of given ranges are 3, 10, 1

Método 1 (Simple)

Una solución simple es ejecutar un ciclo de qs a qe y encontrar GCD en el rango dado. Esta solución toma tiempo O(n) en el peor de los casos.

Método 2 (array 2D)

Otra solución es crear una array 2D donde una entrada [i, j] almacene el GCD en el rango arr[i..j]. El GCD de un rango determinado ahora se puede calcular en un tiempo O(1), pero el preprocesamiento lleva un tiempo O(n^2). Además, este enfoque necesita O (n ^ 2) espacio adicional que puede volverse enorme para arrays de entrada grandes.

Método 3 (árbol de segmentos)

Requisitos previos: conjunto de árboles de segmentos 1 , conjunto de árboles de segmentos 2
El árbol de segmentos se puede utilizar para realizar preprocesamiento y consultas en un tiempo moderado. Con el árbol de segmentos, el tiempo de preprocesamiento es O(n) y el tiempo para la consulta de GCD es O(Logn). El espacio adicional requerido es O(n) para almacenar el árbol de segmentos.

Representación de árboles de segmentos

• Los Nodes hoja son los elementos de la array de entrada.
• Cada Node interno representa GCD de todas las hojas debajo de él.

La representación de array del árbol se utiliza para representar árboles de segmentos, es decir, para cada Node en el índice i,

• El niño izquierdo está en el índice 2*i+1
• Hijo derecho en 2*i+2 y el padre está en el piso ((i-1)/2).

Construcción de un árbol de segmentos a partir de una array dada

• Comience con un segmento arr[0 . . . n-1] y seguir dividiendo en dos mitades. Cada vez que dividimos el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1), llamamos al mismo procedimiento en ambas mitades y, para cada segmento, almacenamos el valor GCD en un Node de árbol de segmento.
• Todos los niveles del árbol de segmentos construido se llenarán por completo excepto el último nivel. Además, el árbol será un árbol binario completo (cada Node tiene 0 o dos hijos) porque siempre dividimos los segmentos en dos mitades en cada nivel.
• Dado que el árbol construido siempre es un árbol binario completo con n hojas, habrá n-1 Nodes internos. Entonces, el número total de Nodes será 2*n – 1.
• La altura del árbol de segmentos será &lceilog ₂ n&rceil. Dado que el árbol se representa mediante una array y se debe mantener la relación entre los índices principal y secundario, el tamaño de la memoria asignada para el árbol de segmentos será 2*2 ^{⌈log ₂ n⌉} – 1

Consulta de GCD de rango dado

/ 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) )
}

A continuación se muestra la implementación de este método:

// 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;
}

Producción:

 GCD of the given range is: 3

Complejidad de tiempo: la complejidad de tiempo para la construcción del árbol es O(n * log(min(a, b))), donde n es el número de modos y a y b son Nodes cuyo GCD se calcula durante la operación de combinación. Hay un total de 2n-1 Nodes, y el valor de cada Node se calcula solo una vez en la construcción del árbol. La complejidad del tiempo para consultar es O (Log n * Log n).
¡Consulte el artículo completo sobre GCD de rangos de índice dados en una array para obtener más detalles!