பிரிவு மரம் மற்றும் Fenwick மரம் (Binary Indexed Tree, BIT) இரண்டும் வரம்பு வினாக்கள் (எ.கா [l, r] மேல் தொகை) மற்றும் புள்ளி புதுப்பித்தல் ஐ O(log n) இல் பதிலளிக்கின்றன, நிரந்தர ஸ்கேனுக்கான O(n) அல்லது முன்னொட்டு தொகை வரிசைக்கான O(n) புதுப்பித்தல்களுடன் ஒப்பிடுகையில்.
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)
பிரிவு மரம் ஒரு இருமப் பணிக்கு தொகுப்பை வரிசையின் ஒவ்வொரு பிரிவுக்கு சேமிக்கிறது, எந்த சமயோபயோகி செயல்பாடும் (தொகை, குறைந்தபட்சம், மாபெரும், gcd) ஆதரிக்கிறது மற்றும், சோம்பேறி பரவலுடன், வரம்பு புதுப்பித்தல்கள் ஆதரிக்கிறது.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | பிரிவு மரம் | |
|---|---|---|
| வினா / புதுப்பித்தல் | O(log n) | O(log n) |
| இடம் | O(n) | O(2n) |
| செயல்பாடுகள் | தொகைகள் (மறுமுறைவிக்கத்தக்க) | எந்த சமயோபயோகி செயல்பாடும் |
| வரம்பு புதுப்பித்தல்கள் | கடினம் | எளிமையாக (சோம்பேறி பரவல்) |
| குறியீட்டு அளவு | சிறிய | பெரிய |
இந்த கட்டமைப்புகள் "ஒரு மதிப்பைப் புதுப்பித்து, பிறகு ஒரு வரம்பு முழுவதும் தொகையை வினவு" வேகமாக்குகின்றன — போட்டி நிரலாக்கம், பகுப்பாய்வு சாளரங்கள், மற்றும் இடைவெளி சிக்கல்களுக்கு அவசியம்.
அவற்றுக்கு இடையே தேர்ந்தெடுப்பது ஒரு வர்த்தக-ஆஃப்: Fenwick மரம் தொகைகளுக்கு சிறிய மற்றும் வேகமானது, அதே சமயம் பிரிவு மரம் குறைந்தபட்சம்/மாபெரும்/வரம்பு-புதுப்பித்தல் பணிச்சுமைக்கு மிகவும் நমনீயமாக உள்ளது.