Dada una array arr[0..n-1]. Es necesario realizar las siguientes operaciones. actualizar (l, r, val) : agrega ‘val’ a todos los elementos en la array desde [l, r]. getRangeSum(l, r) : Encuentra la suma de todos los elementos en el arreglo de [l, r]. Inicialmente, todos los elementos de la array son 0. Las consultas pueden … Continue reading «Árbol indexado binario: actualización de rango y consultas de rango»
Requisito previo: Introducción y DFS La tarea es encontrar LCA de dos Nodes dados en un árbol (no necesariamente un árbol binario). En publicaciones anteriores, hemos visto cómo calcular LCA utilizando el enfoque Sparse Matrix DP . En esta publicación, veremos una optimización realizada en el método Naive mediante la técnica de descomposición sqrt que … Continue reading «Descomposición Sqrt (o Raíz Cuadrada) | Conjunto 2 (LCA de Tree in O(sqrt(height)) tiempo)»
Dada una array arr[] de n números y un entero k, encuentre la longitud de la sub-array mínima con gcd igual a k. Ejemplo: Input: arr[] = {6, 9, 7, 10, 12, 24, 36, 27}, K = 3 Output: 2 Explanation: GCD of subarray {6,9} is 3. GCD of subarray {24,36,27} is also 3, but … Continue reading «Subarreglo más pequeño con GCD dado»
Dado un texto txt[0..n-1] y un patrón pat[0..m-1], escriba una función de búsqueda (char pat[], char txt[]) que imprima todas las apariciones de pat[] en txt []. Puede suponer que n > m. ¿Patrón de preprocesamiento o texto de preprocesamiento? Hemos discutido los siguientes algoritmos en las publicaciones anteriores: Algoritmo KMP Algoritmo Rabin Karp Algoritmo … Continue reading «Búsqueda de patrones utilizando el árbol de sufijos – Part 1»
Dada una array arr[] que consta de N enteros y una array 2D Q[][] que consta de consultas de los siguientes dos tipos: 1 LR: Imprime el conteo de números del rango [L, R] con un solo bit establecido. 2 XV: actualice el elemento de la array en el índice X con V . Ejemplos: … Continue reading «Consultas para contar elementos de array de un rango dado que tienen un solo bit establecido – Part 1»
Dada una array de N enteros, la tarea es realizar las siguientes dos consultas: query(start, end) : Imprime el número de números primos en el subarreglo de principio a fin update(i, x) : actualiza el valor en el índice i a x, es decir, arr[i] = x Ejemplos: Input : arr = {1, 2, 3, … Continue reading «Número de números primos en un subarreglo (con actualizaciones)»
El hash combinado es una técnica para evitar colisiones cuando hay datos de tamaño fijo. Es una combinación de enstringmiento separado y direccionamiento abierto . Utiliza el concepto de direccionamiento abierto (sondeo lineal) para encontrar el primer lugar vacío para el elemento en colisión desde la parte inferior de la tabla hash y el concepto … Continue reading «Hashing fusionado»
Dada una string str de longitud N, y Q consultas de los siguientes dos tipos: (1 LRK): Encuentre el K -ésimo carácter más grande ( no distinto ) del rango de índices [L, R] (indexación basada en 1) (2 JC): Reemplace el carácter J de la string por el carácter C. Ejemplos: Entrada: str = … Continue reading «Consultas para encontrar el K-ésimo carácter más grande en un rango [L, R] de una string con actualizaciones»
Dada una string S de tamaño N. Inicialmente, el valor de count es 0 . La tarea es encontrar el valor de count después de N operaciones para eliminar todos los N caracteres de la string S dada, donde cada operación es: En cada operación, seleccione alfabéticamente el carácter más pequeño de la string S … Continue reading «Encuentre valor después de N operaciones para eliminar N caracteres de la string S con restricciones dadas»
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»