Segmentno drevo in Fenwickovo drevo (Binary Indexed Tree, BIT) oba odgovorita na poizvedbe po obsegih (npr. vsota nad [l, r]) in točkovne posodobitve v O(log n), v primerjavi z O(n) za naivni pregled ali O(n) posodobitve za polje delnih vsot.
Segmentno drevo in Fenwickovo drevo (Binary Indexed Tree, BIT) oba odgovorita na poizvedbe po obsegih (npr. vsota nad [l, r]) in točkovne posodobitve v O(log n), v primerjavi z O(n) za naivni pregled ali O(n) posodobitve za polje delnih vsot.
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)
Segmentno drevo shranjuje agregirane vrednosti za odseke polja v binarnem drevesu in podpira katero koli asociativno operacijo (vsota, najmanjši, največji, gcd) ter s pigmo razširjavo tudi posodobitve po obsegih.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Segmentno drevo | |
|---|---|---|
| Poizvedka / posodobitev | O(log n) | O(log n) |
| Prostor | O(n) | O(2n) |
| Operacije | vsote (invertibilne) | katere koli asociativne operacije |
| Posodobitve po obsegih | težje | enostavno (piga razširjava) |
| Velikost kode | majhna | večja |
Te strukture naredijo "posodobi vrednost, nato pa poizvedi agregirano vrednost po obsegu" hitro — bistvenega pomena za tekmovalno programiranje, okna analitike in probleme s črti.
Izbira med njima je kompromis: Fenwickovo drevo je majhno in hitro za vsote, medtem ko je segmentno drevo bolj prožno za delovanja min/max/posodobitve po obsegih.