Overview
Un árbol de segmentos permite consultas de rango (suma, mínimo, máximo) y actualizaciones de puntos en O(log n).
Analogy
Como un árbol de empresa: el CEO (raíz) conoce el total de la empresa, cada gerente conoce el total de su departamento — actualizar un empleado actualiza hacia arriba.
Step-by-step
- Construye árbol: cada nodo almacena el agregado de su rango
- La raíz cubre [0,n-1]; los hijos cubren mitad izquierda y derecha
- Actualizar posición i: actualiza el camino desde la hoja a la raíz
- Consultar rango [l,r]: combina nodos que cubren exactamente el rango
Visual
[1,3,5,7,9,11]
Raíz: suma[0..5]=36
Izq: suma[0..2]=9, Der: suma[3..5]=27
Common mistakes
- Tamaño del array del árbol: necesitas 4n, no 2n
- Lógica de consulta de rango incorrecta — manejar l>r correctamente
Practice questions
- Implementa árbol de segmentos de suma con actualización puntual
- Extiende a consultas de rango mínimo
Time
O(n) construcción, O(log n) consulta y actualización
Space
O(n) — el árbol tiene 4n nodos