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 2 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 2 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++
// 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 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
Javascript
<script>
// Javascript Program to find GCD of a number in a given Range
// using segment Trees
let 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 */
function constructSegmentTree(arr) {
let height = Math.floor(Math.ceil(Math.log(arr.length) / Math.log(2)));
let size = 2 * Math.pow(2, height) - 1;
st = new Array(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
function constructST(arr, ss, se, si) {
if (ss == se) {
st[si] = arr[ss];
return st[si];
}
let mid = Math.floor(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.
function gcd(a, b) {
if (a < b) {
// If b greater than a swap a and b
let temp = b;
b = a;
a = temp;
}
if (b == 0)
return a;
return gcd(b, a % b);
}
//Finding The gcd of given Range
function findRangeGcd(ss, se, arr) {
let n = arr.length;
if (ss < 0 || se > n - 1 || ss > se)
throw new Error("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 */
function findGcd(ss, se, qs, qe, si) {
if (ss > qe || se < qs)
return 0;
if (qs <= ss && qe >= se)
return st[si];
let mid = Math.floor(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
let a = [2, 3, 6, 9, 5]
constructSegmentTree(a);
let l = 1; // Starting index of range.
let r = 3; //Last index of range.
document.write("GCD of the given range is: ");
document.write(findRangeGcd(l, r, a));
// This code is contributed by saurabh_jaiswaal.
</script>
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). Este artículo es una contribución de Nikhil Tekwani . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA