Un arbore de segmente și un arbore Fenwick (Binary Indexed Tree, BIT) răspund atât interogărilor de interval (de ex. suma peste [l, r]) cât și actualizărilor punctuale în O(log n), versus O(n) pentru o scanare naivă sau actualizări O(n) pentru o matrice de sumă de prefix.
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 arbore de segmente stochează o valoare agregată per segment de matrice într-un arbore binar, susținând orice operație asociativă (suma, min, max, gcd) și, cu lazy propagation, și actualizări de interval.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Arbore de segmente | |
|---|---|---|
| Interogare / actualizare | O(log n) | O(log n) |
| Spațiu | O(n) | O(2n) |
| Operații | sume (inversabile) | orice operație asociativă |
| Actualizări de interval | mai dificil | ușor (lazy propagation) |
| Dimensiunea codului | diminutiv | mai mare |
Aceste structuri fac "actualizează o valoare, apoi interogheaza o valoare agregată peste un interval" rapid — esențial pentru programarea competitivă, ferestre analitice și probleme de interval.
Alegerea între ele este un compromis: un arbore Fenwick este mic și rapid pentru sume, în timp ce un arbore de segmente este mai flexibil pentru sarcini de lucru min/max/actualizare-interval.