Un árbol de segmentos y un árbol de Fenwick (Binary Indexed Tree, BIT) responden tanto consultas de rango (p. ej., suma sobre [l, r]) como actualizaciones puntuales en , frente a O(n) para un escaneo ingenuo o actualizaciones O(n) para un array de suma de prefijos.
Array + many "sum of range [l,r]" and "update index i" calls:
naive prefix sums: query O(1) but UPDATE is O(n)
segment/Fenwick: query O(log n) AND update O(log n)
class Fenwick:
def __init__(self, n):
self.t = [0]*(n+1)
def update(self, i, delta): # O(log n)
i += 1
while i < len(self.t):
self.t[i] += delta
i += i & (-i) # jump to next responsible node
def prefix(self, i): # sum of [0..i], O(log n)
i += 1; s = 0
while i > 0:
s += self.t[i]
i -= i & (-i)
return s
def range_sum(self, l, r):
return self.prefix(r) - self.prefix(l-1)
Un árbol de segmentos almacena un agregado por cada segmento de array en un árbol binario, admitiendo cualquier operación asociativa (suma, mínimo, máximo, gcd) y, con propagación perezosa, también actualizaciones de rango.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Árbol de segmentos | |
|---|---|---|
| Consulta / actualización | O(log n) | O(log n) |
| Espacio | O(n) | O(2n) |
| Operaciones | sumas (invertibles) | cualquier operación asociativa |
| Actualizaciones de rango | más difícil | fácil (propagación perezosa) |
| Tamaño de código | minúsculo | más grande |
Estas estructuras hacen que "actualizar un valor, luego consultar un agregado sobre un rango" sea rápido — esencial para programación competitiva, ventanas analíticas y problemas de intervalos.
Elegir entre ellas es una compensación: un árbol de Fenwick es pequeño y rápido para sumas, mientras que un árbol de segmentos es más flexible para cargas de trabajo min/max/actualización de rango.