సెగ్మెంట్ చెట్ మరియు ఫెన్విక్ చెట్ (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) |
| కార్యక్రమాలు | మొత్తాలు (విలోమ) | ఏదైనా సంబంధిత కార్యక్రమం |
| పరిధి నవీకరణలు | కష్టతర | సులభం (సోమరి ప్రచారం) |
| కోడ్ పరిమాణం | చిన్న | పెద్ద |
ఈ నిర్మాణాలు "విలువను నవీకరించు, ఆ తర్వాత ఒక పరిధిపై సమీకరణను ప్రశ్నించు" వేగవంతం చేస్తాయి — పోటీ ప్రోగ్రామింగ్, విశ్లేషణ విండోలు, మరియు విరామ సమస్యల కోసం అవసరం.
వారి మధ్య ఎంపిక ఒక ట్రేడ్-ఆఫ్: ఫెన్విక్ చెట్ మొత్తాల కోసం చిన్న మరియు వేగవంతం, సెగ్మెంట్ చెట్ కనీసం/గరిష్ట/పరిధి-నవీకరణ పని చరుస్సుల కోసం మరింత నమనీయమైనది.