Mti wa sehemu na mti wa Fenwick (Binary Indexed Tree, BIT) wote wanajaza maswali ya anuwai (k.m. jumla juu ya [l, r]) na sasisho la nukta katika O(log n), ikilinganishwa na O(n) kwa ujanibishaji usiotaka au O(n) sasisho kwa safu ya jumla ya awali.
Mti wa sehemu na mti wa Fenwick (Binary Indexed Tree, BIT) wote wanajaza maswali ya anuwai (k.m. jumla juu ya [l, r]) na sasisho la nukta katika O(log n), ikilinganishwa na O(n) kwa ujanibishaji usiotaka au O(n) sasisho kwa safu ya jumla ya awali.
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)
Mti wa sehemu hufanya hifadhi ya jumla kwa kila sehemu ya safu katika mti wa jozi, unashirikiana na utendaji wowote wa ushirikiano (jumla, kiwango, upeo, gcd) na, kwa kueneza kwa pelele, pia masasisho ya anuwai.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Mti wa sehemu | |
|---|---|---|
| Swali / sasisho | O(log n) | O(log n) |
| Nafasi | O(n) | O(2n) |
| Utendaji | jumla (zinageuka) | utendaji wowote wa ushirikiano |
| Masasisho ya anuwai | ngumu | rahisi (kueneza kwa pelele) |
| Ukubwa wa nambari | ndogo | kubwa |
Hizi miundo hufanya "sasisho linalokaa thamani, kisha uliza jumla juu ya anuwai" haraka — muhimu kwa programu ya mgogoro, madirisha ya uchambuzi, na matatizo ya muda.
Kuchagua baina yao ni kompromiso: mti wa Fenwick ni ndogo na haraka kwa jumla, wakati mti wa sehemu ni mwenyezi zaidi kwa min/max/masasisho ya anuwai.