Un segment tree e un Fenwick tree (Binary Indexed Tree, BIT) rispondono a query di intervallo (es. somma su [l, r]) e a aggiornamenti puntuali in O(log n), rispetto a O(n) per una scansione ingenua o O(n) per aggiornamenti in un array di somme prefisse.
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 segment tree memorizza un aggregato per segmento di array in un albero binario, supportando qualsiasi operazione associativa (somma, min, max, gcd) e, con lazy propagation, aggiornamenti di intervallo altrettanto.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Segment tree | |
|---|---|---|
| Query / aggiornamento | O(log n) | O(log n) |
| Spazio | O(n) | O(2n) |
| Operazioni | somme (invertibili) | qualsiasi operazione associativa |
| Aggiornamenti di intervallo | più difficili | facili (lazy propagation) |
| Dimensione codice | minuscola | più grande |
Queste strutture rendono "aggiorna un valore, poi interroga un aggregato su un intervallo" veloce — essenziale per la programmazione competitiva, finestre di analytics e problemi di intervalli.
La scelta tra loro è un compromesso: un Fenwick tree è minuscolo e veloce per le somme, mentre un segment tree è più flessibile per carichi di lavoro min/max/aggiornamento di intervallo.