Árbol de segmentos: construcción y consultas
Obtenga el mínimo, máximo o total de un rango en log n
Árbol de segmentos: construcción y consultas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Más allá del árbol de Fenwick
Un árbol de Fenwick destaca para las sumas, pero un árbol de segmentos admite mínimos, máximos, mcd y mucho más. Es la herramienta flexible por excelencia para las consultas de rangos.
Un árbol sobre rangos
Cada nodo posee un rango del array. La raíz lo cubre por completo; los hijos lo dividen por la mitad hasta que las hojas contienen elementos individuales.
Almacenamiento respaldado por un array
Almacenamos el árbol en un array plano de tamaño 2n o 4n. El nodo 1 es la raíz; los hijos del nodo i están en 2i y 2i+1.
seg = [0] * (2 * n)Las hojas contienen los datos
En la versión iterativa, los valores originales viven en la segunda mitad del array, en los índices n a 2n-1.
for i in range(n):
seg[n + i] = a[i]Construir desde abajo hacia arriba
Cada nodo interno es la operación combine de sus dos hijos. Rellénelos desde n-1 hasta 1 y todo el árbol estará listo.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]La operación combine
La función combine define el árbol. Use plus para las sumas, min para los mínimos o max para los máximos. Cámbiela para modificar la consulta.
def combine(x, y):
return min(x, y)Actualizar un punto y subir
Para cambiar un valor, establezca la hoja y suba hasta la raíz, recalculando por el camino cada padre a partir de sus dos hijos.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Consultar un rango semiabierto
Las consultas de rangos recorren ambos extremos y combinan los nodos de los límites en la respuesta. El intervalo es semiabierto: incluye l, pero no r.
El bucle de consulta iterativo
Mueva l y r acercándolos entre sí. Cuando un índice sea un límite impar, incorpore ese nodo antes de avanzar el puntero.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2Logarítmico en ambos extremos
La construcción cuesta O(n), mientras que cada actualización y consulta cuesta O(log n). Ese equilibrio hace que los árboles de segmentos sean tan versátiles.
No olvide el elemento neutro
Inicie el resultado con el elemento neutro de la operación: 0 para la suma, infinito para el mínimo y menos infinito para el máximo. Empezar con el valor incorrecto produce respuestas incorrectas.
res = float('inf')Comprobación rápida
¿Dónde se encuentran los datos originales en el árbol iterativo?
Repaso: rangos flexibles
Construyó un árbol de segmentos: hojas en la segunda mitad, padres como operaciones combine y actualizaciones y consultas en O(log n) para sumas, mínimos o máximos. 🌳
Preguntas frecuentes
¿La lección «Árbol de segmentos: construcción y consultas» es gratis?
Sí — el texto completo de «Árbol de segmentos: construcción y consultas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Árbol de segmentos: construcción y consultas»?
Obtenga el mínimo, máximo o total de un rango en log n Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Árbol de segmentos: construcción y consultas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Árbol de Fenwick para sumas prefijas
- Inversiones con un BIT
- Árbol de segmentos: construcción y consultas
- Propagación diferida para actualizaciones de rangos