segmentų medis ir Fenviko medis (Binary Indexed Tree, BIT) abu atsakinėja diapazonų užklausas (pvz. sumą per [l, r]) ir taškiškus atnaujinimus per O(log n), priešingai nei O(n) grynai skenavimui arba O(n) prefikso sumos masyvo atnaujinimams.
segmentų medis ir Fenviko medis (Binary Indexed Tree, BIT) abu atsakinėja diapazonų užklausas (pvz. sumą per [l, r]) ir taškiškus atnaujinimus per O(log n), priešingai nei O(n) grynai skenavimui arba O(n) prefikso sumos masyvo atnaujinimams.
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)
Segmentų medis kiekviename masyvo segmente saugo suvestinę dvejetainiame medyje, palaikydamas bet kokią asociatyvinę operaciją (sumą, minimumą, maksimumą, dbd) ir, naudodamas tūlintąją propagaciją, diapazonų atnaujinimus taip pat.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenviko (BIT) | Segmentų medis | |
|---|---|---|
| Užklausa / atnaujinimas | O(log n) | O(log n) |
| Vieta | O(n) | O(2n) |
| Operacijos | sumos (grįžtamos) | bet kokia asociatyvinė operacija |
| Diapazonų atnaujinimai | sunkiau | lengva (tūlintoji propagacija) |
| Kodo dydis | labai mažas | didesnis |
Šios struktūros pagreitina "atnaujinti reikšmę, tada užklausti suvestinę diapazone" — esminė konkurencingojoje programavimoje, analitikos languose ir intervalų problemose.
Pasirinkimas tarp jų yra kompromisas: Fenviko medis yra mažas ir greitas sumoms, o segmentų medis yra lankstesnis min/max/diapazonų atnaujinimo darbo krūviams.