Publicado · en mejora
Algorithm
Un árbol de segmentos responde consultas de suma o mínimo en un rango y actualiza valores en O(log n); el árbol de Fenwick es su alternativa ligera para sumas.
Un árbol de segmentos es un árbol binario que guarda un resumen, como la suma, el mínimo o el máximo, de cada rango que resulta de dividir un arreglo por la mitad una y otra vez. La raíz cubre todo el arreglo, cada hoja cubre un solo elemento y cada nodo interno combina a sus dos hijos. Así, cualquier pregunta sobre un rango contiguo se responde combinando unos pocos nodos.
Las sumas prefijas responden sumas de rango en O(1), pero necesitan O(n) para absorber un solo cambio; un arreglo sin más se actualiza al instante, pero cada consulta cuesta O(n). Un árbol de segmentos resuelve tanto las actualizaciones puntuales como las consultas de rango en O(log n), por lo que es la herramienta adecuada cuando los valores cambian sin parar y las consultas no dejan de llegar. Con propagación perezosa también admite actualizaciones de rango, como sumar un valor a todo un tramo, en O(log n).
Conviene empezar por entender dónde fallan las sumas prefijas, dibujar a mano un árbol pequeño y seguir qué nodos recorren una consulta y una actualización. Después, escribe tú mismo la implementación iterativa corta y un árbol de Fenwick, y practica con problemas clásicos como el mínimo en un rango, el conteo de inversiones y la suma en rango con actualizaciones de rango.
Cada nodo se encarga de un rango del arreglo y guarda su suma o su mínimo; cualquier operación asociativa con elemento neutro encaja en la misma estructura.
Cambiar un elemento solo recalcula un camino de la hoja a la raíz, y una consulta de rango combina como mucho dos nodos por nivel.
Una actualización de rango deja una nota en los nodos que la cubren y solo la pasa a los hijos cuando una operación necesita descender.
Para operaciones invertibles como la suma, un árbol de Fenwick (BIT) logra la misma complejidad con un arreglo de n + 1 posiciones y unos pocos bucles cortos.
Un árbol de segmentos iterativo: los elementos ocupan la segunda mitad de un arreglo de tamaño 2n y cada posición anterior guarda la suma de sus dos hijos. update sube de la hoja a la raíz recalculando sumas, y query sube desde los dos extremos del rango semiabierto [left, right) sumando solo los nodos del borde. Al ejecutarlo imprime 26, 17 y 28.
segment_tree.py
class SegmentTree:
"""Iterative segment tree: point update and range sum in O(log n)."""
def __init__(self, values):
self.n = len(values)
self.tree = [0] * self.n + list(values)
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, index, value):
i = index + self.n
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, left, right):
"""Sum of values[left:right] (half-open range)."""
total = 0
lo, hi = left + self.n, right + self.n
while lo < hi:
if lo & 1:
total += self.tree[lo]
lo += 1
if hi & 1:
hi -= 1
total += self.tree[hi]
lo //= 2
hi //= 2
return total
if __name__ == "__main__":
tree = SegmentTree([5, 3, 7, 9, 6, 4, 1, 2])
print(tree.query(2, 6)) # 7 + 9 + 6 + 4 = 26
tree.update(3, 0)
print(tree.query(2, 6)) # 7 + 0 + 6 + 4 = 17
print(tree.query(0, 8)) # 28
python segment_tree.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Árboles de segmentos.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Árboles de segmentos.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.