Dada una array arr[0 . . . n-1]. La tarea es realizar la siguiente operación: Encuentre el máximo de elementos del índice l a r donde 0 <= l <= r <= n-1. Cambia el valor de un elemento específico de la array a un nuevo valor x. Dados i y x, cambie A[i] por … Continue reading «Árbol de segmentos iterativos (consulta de rango máximo con actualización de Node)»
Dada una array arr[] de N elementos y un número de consultas donde cada consulta contendrá tres números enteros L , R y K . Para cada consulta, la tarea es encontrar el número de elementos en el subarreglo arr[L…R] que son mayores que K . Ejemplos: Entrada: arr[] = {7, 3, 9, 13, 5, … Continue reading «Consultas de elementos mayores que K en el rango de índice dado usando Segment Tree»
Euler Tour Tree (ETT) es un método para representar un árbol con raíz como una secuencia numérica. Al atravesar el árbol usando Profundidad para búsqueda (DFS) , inserte cada Node en un vector dos veces, una vez mientras lo ingresa y la siguiente después de visitar todos sus elementos secundarios. Este método es muy útil … Continue reading «Tour de Euler | Suma de subárbol utilizando el árbol de segmentos»
Un árbol de segmentos alternos GCD/LCM Levelwise es un árbol de segmentos, de modo que en cada nivel se alternan las operaciones GCD y LCM. En otras palabras, en el nivel 1, los subárboles izquierdo y derecho se combinan mediante la operación GCD, es decir, Node principal = hijo izquierdo GCD derecho secundario y en … Continue reading «GCD y LCM alternos por niveles de Nodes en el árbol de segmentos»
Dada una array de tamaño N. Puede haber múltiples consultas de los siguientes tipos. actualizar (l, r) : en la actualización, voltea (multiplica a[i] por -1) el valor de a[i] donde l <= i <= r . En términos simples, cambie el signo de a[i] para el rango dado. consulta (l, r) : en la … Continue reading «Problema de señal de volteo | Árbol de segmentos de propagación diferida»
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: … Continue reading «Programa Java para encontrar los GCD de rangos de índice dados en una array»
Dada una array rectangular M[0…n-1][0…m-1] , y se solicitan consultas para encontrar la suma / mínimo / máximo en algunos sub-rectángulos M[a…b][e…f] , como así como consultas para la modificación de elementos de array individuales (es decir , M[x] [y] = p ). También podemos responder consultas de subarrays utilizando el árbol indexado binario bidimensional … Continue reading «Árbol de segmento bidimensional | Suma de subarray»
Tenemos una array arr[0 . . . n-1]. Deberíamos poder encontrar de manera eficiente el valor mínimo desde el índice L (inicio de consulta) hasta R (final de consulta) donde 0 <= L <= R <= n-1 . Considere una situación en la que hay muchas consultas de rango. Ejemplo: Input: arr[] = {7, 2, 3, … Continue reading «Consulta de rango mínimo (descomposición de raíz cuadrada y tabla dispersa)»
Dadas consultas Q, de tipo: LR , para cada consulta debe imprimir el número máximo de divisores que tiene un número x (L <= x <= R) . Ejemplos: L = 1 R = 10: 1 has 1 divisor. 2 has 2 divisors. 3 has 2 divisors. 4 has 3 divisors. 5 has 2 divisors. 6 … Continue reading «Consultar el número máximo de divisores que tiene un número en un rango dado»
Dada una array arr[] de N enteros y Q consultas, cada consulta tiene dos enteros L y R , la tarea es encontrar el elemento que tiene el máximo de bits establecidos en el rango L a R. Nota: Si hay varios elementos que tienen un número máximo de bits establecidos, imprima el máximo de … Continue reading «Encuentre el elemento que tiene un conjunto máximo de bits en el rango dado para consultas Q»