Requisito previo: Árbol de segmentos y búsqueda en profundidad primero . En este artículo, se analiza un enfoque para convertir un árbol con raíz N-aria (un árbol con más de 2 hijos) en un árbol de segmento que se utiliza para realizar consultas de actualización de rango. ¿Por qué necesitamos un árbol de segmentos cuando ya … Continue reading «Construya un árbol de segmentos para un árbol con raíz N-aria»
Dada una array no ordenada, recorte la array de modo que el doble del mínimo sea mayor que el máximo en la array recortada. Los elementos deben eliminarse de cualquier extremo de la array. El número de retiros debe ser mínimo. Ejemplos: Entrada: arr[] = {4, 5, 100, 9, 10, 11, 12, 15, 200} Salida: … Continue reading «Eliminar los elementos mínimos de ambos lados de modo que 2*min se convierta en más que max | conjunto 2»
Dada una array A[] , para cada elemento de la array, la tarea es encontrar la suma de todos los elementos anteriores que son estrictamente mayores que el elemento actual. Ejemplos: Entrada: A[] = {2, 6, 4, 1, 7} Salida: 0 0 6 12 0 Explicación: Para 2 y 6 no hay ningún elemento mayor … Continue reading «Suma de números anteriores que son mayores que el número actual para una array dada»
Dada una array A[] de longitud N , donde N es un número par, la tarea es responder Q consultas independientes donde cada consulta consiste en un número entero positivo K que representa el número de desplazamientos circulares realizados en la array y encontrar la suma de elementos realizando la operación Bitwise OR en la … Continue reading «Programa Python3 para encontrar la suma de la array usando Bitwise O después de dividir la array dada en dos mitades después de K cambios circulares»
Hemos introducido el árbol de segmentos con un ejemplo simple en la publicación anterior. En esta publicación, el problema de consulta de rango mínimo se analiza como otro ejemplo en el que se puede usar el árbol de segmentos. El siguiente es el enunciado del problema: Tenemos un arreglo arr[0 . . . n-1]. Deberíamos … Continue reading «Árbol de segmentos | Conjunto 2 (consulta de rango mínimo)»
Dada una array arr[] de N enteros, la tarea es realizar las siguientes dos consultas: consulta (inicio, final) : imprime la cantidad de números de Fibonacci en el subarreglo de principio a fin update(i, x) : agregue x al elemento de array al que hace referencia el índice de array i , es decir: arr[i] … Continue reading «Consultas de rango de array para contar la cantidad de números de Fibonacci con actualizaciones»
Dado inicialmente un conjunto vacío y una serie de consultas sobre él, cada una posiblemente de los siguientes tipos: Insertar : inserta un nuevo elemento ‘x’. Eliminar : elimina un elemento existente ‘x’. Mediana : imprime el elemento mediano de los números actualmente en el conjunto Ejemplo: Input : Insert 1 Insert 4 Insert 7 … Continue reading «Diseñe eficientemente consultas de inserción, eliminación y mediana en un conjunto»
Dada una array ‘arr’, cuyos números se inicializan en ‘0’, la array se puede actualizar en cualquier momento de la siguiente manera: Todos los elementos de cualquier sub-array de la array se pueden voltear, es decir, ‘1’ = > ‘0’ o ‘0’ => ‘1’. La tarea es encontrar el número de 1 de la array para … Continue reading «Consultas de rango para contar 1 en un subarreglo después de las operaciones de volteo»
Dada una string de corchetes, la tarea es encontrar el número de pares de corchetes involucrados en una secuencia balanceada en un rango dado. Ejemplos: Input : ((())(() Range : 1 5 Range : 3 8 Output : 2 2 Explanation : In range 1 to 5 ((()), there are the two pairs. In range … Continue reading «Pares involucrados en Paréntesis Equilibrados»
Hemos discutido la implementación del árbol de segmentos recursivos . En esta publicación, se analiza la implementación iterativa. Consideremos el siguiente problema para comprender los árboles de segmentos. Tenemos una array arr[0 . . . n-1]. Deberíamos poder 1 Encontrar el mínimo de elementos del índice l a r donde 0 <= l <= r … Continue reading «Árbol de segmentos iterativos (consulta de rango mínimo)»