एक सेगमेंट ट्री और एक फेनविक ट्री (Binary Indexed Tree, BIT) दोनों ही रेंज क्वेरीज़ (उदा. [l, r] पर योग) और पॉइंट अपडेट्स को O(log n) में जवाब देते हैं, जो सरल स्कैन के O(n) या प्रीफिक्स-सम ऐरे के O(n) अपडेट्स की तुलना में है।
एक सेगमेंट ट्री और एक फेनविक ट्री (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
| फेनविक (BIT) | सेगमेंट ट्री | |
|---|---|---|
| क्वेरी / अपडेट | O(log n) | O(log n) |
| स्पेस | O(n) | O(2n) |
| ऑपरेशन्स | योग (उल्टे) | कोई भी एसोशिएटिव ऑप |
| रेंज अपडेट्स | कठिन | आसान (lazy propagation) |
| कोड साइज़ | बहुत छोटा | बड़ा |
ये संरचनाएं "एक मान को अपडेट करें, फिर किसी रेंज पर एग्रीगेट को क्वेरी करें" को तेज़ बनाती हैं — प्रतिस्पर्धी प्रोग्रामिंग, विश्लेषण विंडो और अंतराल समस्याओं के लिए आवश्यक।
उनके बीच चुनना एक ट्रेड-ऑफ है: फेनविक ट्री योग के लिए छोटा और तेज़ है, जबकि सेगमेंट ट्री न्यूनतम/अधिकतम/रेंज-अपडेट कार्यभार के लिए अधिक लचीला है।