सेगमेंट ट्री आणि फेनविक ट्री (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) |
| ऑपरेशन | बेरीज (उलटवता येणारी) | कोणताही सहयोगी ऑपरेशन |
| श्रेणी अपडेट | कठीण | सोपे (आळस प्रसारण) |
| कोड आकार | अतिशय लहान | मोठे |
हे संरचनाएं "मूल्य अपडेट करा, नंतर श्रेणी पर एकीकरण प्रश्न करा" वेगवान बनवतात — प्रतिस्पर्धी प्रोग्रामिंग, विश्लेषण खिडकी आणि अंतराल समस्यांसाठी आवश्यक।
त्यांच्या दरम्यान निवड करणे हा व्यापार-बंद आहे: फेनविक ट्री बेरीजसाठी लहान आणि वेगवान आहे, तर सेगमेंट ट्री किमान/कमाल/श्रेणी-अपडेट कार्यभारांसाठी अधिक लचकदार आहे।