Një pemë segmentale dhe një pemë Fenwick (Binary Indexed Tree, BIT) të dyja përgjigjen pyetjet mbi diapazonet (p.sh. shuma mbi [l, r]) dhe përditësimet e pikës në O(log n), në krahasim me O(n) për një skanim naiv ose O(n) përditësime për një grup shumash paraprake.
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)
Një pemë segmentale ruaj një agregat për secilin segment të vargut në një pemë binare, duke mbështetlur ndonjë operacion shoqërues (shuma, minimumi, maksimumi, gcd) dhe, me përhapjen e pijazy, edhe përditësimet mbi diapazonet.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Pemë segmentale | |
|---|---|---|
| Pyetja / përditësimi | O(log n) | O(log n) |
| Hapësira | O(n) | O(2n) |
| Operacione | shumat (të zëvendësueshme) | ndonjë operacion shoqërues |
| Përditësimet mbi diapazonet | më e vështirë | e lehtë (përhapja e pijazy) |
| Madhësia e kodit | e vogël | më e madhe |
Këto struktura e bëjnë "përditëso një vlerë, pastaj kërkoji një agregat mbi një diapazon" të shpejtë — thelbësore për programimin kompetitiv, dritaret e analitikës dhe problemet e intervalit.
Zgjedhja midis tyre është një kompromis: një pemë Fenwick është e vogël dhe e shpejtë për shumat, ndërsa një pemë segmentale është më fleksibël për min/max/përditësimet mbi diapazonet.