Uma árvore de segmentos e uma árvore de Fenwick (Binary Indexed Tree, BIT) respondem tanto consultas de intervalo (p.ex. soma sobre [l, r]) quanto atualizações pontuais em , versus O(n) para uma varredura ingênua ou atualizações O(n) para uma matriz de soma de prefixo.
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)
Uma árvore de segmentos armazena um agregado por segmento de matriz em uma árvore binária, suportando qualquer operação associativa (soma, mín, máx, mdc) e, com lazy propagation, também atualizações de intervalo.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Árvore de segmentos | |
|---|---|---|
| Consulta / atualização | O(log n) | O(log n) |
| Espaço | O(n) | O(2n) |
| Operações | somas (invertíveis) | qualquer operação associativa |
| Atualizações de intervalo | mais difícil | fácil (lazy propagation) |
| Tamanho do código | minúsculo | maior |
Essas estruturas tornam "atualizar um valor, então consultar um agregado sobre um intervalo" rápido — essencial para programação competitiva, janelas analíticas e problemas de intervalo.
Escolher entre elas é uma compensação: uma árvore de Fenwick é minúscula e rápida para somas, enquanto uma árvore de segmentos é mais flexível para cargas de trabalho de mín/máx/atualização de intervalo.