Los árboles de intervalo son árboles que permiten consultar en rangos insertados. Por ejemplo, inserte los rangos (10, 20), (15, 40) y pregunte si hay algún rango que alcance el valor 12 o un rango como (9, 11), etc.
Un árbol de rango también es algo similar, excepto que las entidades insertadas son puntos y no rangos como en el árbol de intervalos.
Un BIT (árbol indexado binario) es un árbol nocional que permite calcular sumas de rango rápidamente. Es solo una forma de almacenar sumas en algún subconjunto de intervalos que le permite construir la suma sobre cualquier intervalo con estos subconjuntos de suma de intervalos precalculados. No puede usar un BIT para calcular consultas de rango mínimo o máximo ya que lo único que puede hacer con un BIT es calcular la suma / min / max de un rango que comienza desde el índice 0 (inicio del intervalo). Para la suma de rango en el rango (a, b), se puede calcular la suma como suma (0, b) – suma (0, a), sin embargo, el mismo truco no se puede usar para min / max.
- ¿Cómo se escriben funciones explícitas y recursivas cuando se les da un conjunto particular de datos?
- ¿Por qué no se utilizan algoritmos genéticos?
- ¿Para qué aplicaciones son especialmente adecuados los lenguajes de programación lógica? ¿Cuándo usarías un lenguaje como Prolog? ¿Cuáles son las aplicaciones más exitosas de la programación lógica?
- ¿Cuáles son algunas de las preguntas de cadena que se hacen comúnmente en una entrevista técnica?
- ¿Cómo se comunican los dispositivos GPS con los servidores?
Un árbol de segmentos es una noción más general de un BIT, donde uno calcula previamente la suma sobre un conjunto fijo de rangos (no necesariamente a partir del índice 0), lo que permite que una capa O (log n) dichos rangos calcule la suma / min / max sobre cualquier rango arbitrario.
Todas las estructuras se pueden implementar de manera bastante eficiente con los costos de consulta / actualización de O (log n), siendo n el número de puntos / rangos insertados en la estructura. Por supuesto, las consultas de informes de rango (sin contar) tomarán más tiempo ya que debe informar los rangos O (k), por lo que la complejidad sube a Ω (k + log n) en estos casos (suponiendo que tengamos k rangos para informar, por supuesto) )
En lo que respecta a la implementación de árboles de rango / intervalo / segmento , se puede aumentar cualquier estructura de árbol equilibrada, como árboles AVL, árboles RB, Treaps o incluso una lista de salto y obtener los límites amortizados mencionados anteriormente. Consulte el algoritmo-js para ver un ejemplo de cómo aumentar los árboles AVL para implementar árboles de suma de rango. Puedes usar un truco similar para cambiarlo a árboles de rango mínimo / máximo.
Consulte http://dhruvbird.com/Skip-List-R… para tener una idea de cómo implementar las consultas de rango utilizando las listas de omisión.
Los programadores en concursos de programación generalmente implementan árboles de segmentos utilizando una matriz estática sobre el rango de valores de entrada (y no el número de entidades). Esto da como resultado una estructura que es O (el rango de valores) [espacio] en lugar de O (el número de entidades) a menos que uno tenga cuidado de asegurarse de que el rango de valores ∈ O (número de entidades de entrada). Vea Árbol de segmentos – PEGWiki para más detalles sobre la construcción del Árbol de segmentos en una configuración de concurso de programación.
