Drzewo segmentowe i drzewo Fenwicka (Binary Indexed Tree, BIT) odpowiadają zarówno na zapytania o zakresie (np. suma w [l, r]) jak i aktualizacje punktowe w O(log n), w porównaniu do O(n) dla naiwnego skanowania lub O(n) aktualizacji dla tablicy sum prefiksowych.
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)
Drzewo segmentowe przechowuje wartość zagregowaną na segment tablicy w drzewie binarnym, wspierając dowolną operację asocjacyjną (suma, min, max, gcd) i, z lazy propagation, również aktualizacje zakresu.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwicka (BIT) | Drzewo segmentowe | |
|---|---|---|
| Zapytanie / aktualizacja | O(log n) | O(log n) |
| Pamięć | O(n) | O(2n) |
| Operacje | sumy (odwracalne) | dowolna operacja asocjacyjna |
| Aktualizacje zakresu | trudniej | łatwo (lazy propagation) |
| Rozmiar kodu | mały | większy |
Te struktury sprawiają, że "aktualizacja wartości, a następnie zapytanie o wartość zagregowaną w zakresie" jest szybkie — niezbędne dla programowania konkurencyjnego, okien analitycznych i problemów interwałowych.
Wybór między nimi jest kompromisem: drzewo Fenwicka jest małe i szybkie dla sum, podczas gdy drzewo segmentowe jest bardziej elastyczne dla obciążeń min/max/zakres-aktualizacja.
Biblioteka pytań rekrutacyjnych IT ze szczegółowymi odpowiedziami — od Juniora do Seniora.
Wesprzyj