Dada una array de enteros con rango limitado (0 a 1000000). Necesitamos implementar un árbol de estadísticas de pedidos usando el árbol fenwick. Debe soportar cuatro operaciones: Insertar, Eliminar, Seleccionar y Clasificar. Aquí n denota el tamaño del árbol de Fenwick y q denota el número de consultas. Cada consulta debe ser una de las siguientes … Continue reading «Ordene el árbol estadístico usando el árbol fenwick (BIT)»
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)»
Dado un árbol binario, la tarea es encontrar la distancia entre dos claves en un árbol binario, no se dan punteros principales. La distancia entre dos Nodes es el número mínimo de aristas a recorrer para llegar a un Node desde otro. Ya hemos discutido un método que usa el árbol de segmentos para reducir … Continue reading «Consultas para encontrar la distancia entre dos Nodes de un árbol binario – Part 1»
Dada la representación de la Lista de Adyacencia de un árbol y un número entero K ., la tarea es encontrar si el árbol dado se puede dividir en K Componentes Conectados iguales o no. Nota : se dice que dos componentes conectados son iguales si contienen el mismo número de Nodes. Ejemplos: Entrada: N … Continue reading «Compruebe si un árbol se puede dividir en K componentes conectados iguales»
Requisito previo: convertir una array en una lista circular doblemente vinculada , lista doblemente circular dada una lista doblemente circular. La tarea es encontrar la posición de un elemento en la lista. Representación de la imagen : Algoritmo: Declare un puntero temporal e inicialícelo en el encabezado de la lista. Repita el bucle hasta que … Continue reading «Buscar un elemento en una lista enlazada doblemente circular»
Dada una array de N enteros, la tarea es realizar las siguientes dos operaciones en la array dada: consulta (inicio, fin) : imprime el número de números compuestos en el subarreglo de principio a fin actualización (i, x) : actualiza el valor en el índice i a x, es decir, arr [i] = x Ejemplos … Continue reading «Consultas de números compuestos en subarreglo (con actualizaciones de puntos)»
Dado un árbol N-ario que consta de N Nodes con valores de 1 a N enraizados en 1, para todos los Nodes, imprima el número de ancestros que tienen un valor menor que el Node actual. Ejemplo: Entrada: A continuación se muestra el árbol dado: … Continue reading «Recuento de ancestros con menor valor para cada Node de un árbol N-ario»
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 C++ para encontrar los GCD de rangos de índice dados en una array»
Dada una array de enteros, ordene la array de acuerdo con la frecuencia de los elementos en orden decreciente, si la frecuencia de dos elementos es la misma, entonces ordene en orden creciente Ejemplos: Input: arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12} Output: 3 3 3 3 2 2 … Continue reading «Ordenar elementos por frecuencia | Conjunto 5 (usando Java Map)»
Recomendamos encarecidamente leer la siguiente publicación sobre árboles de sufijos como requisito previo para esta publicación. Búsqueda de patrones | Conjunto 8 (Introducción al árbol de sufijos) Una array de sufijos es una array ordenada de todos los sufijos de una string dada . La definición es similar a Suffix Tree, que se comprime de … Continue reading «Array de sufijos | Serie 1 (Introducción)»