સેગમેન્ટ ટ્રી અને ફેનવિક ટ્રી (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) |
| કોડ કદ | ખૂબ જ નાનું | મોટું |
આ સંરચનાઓ "મૂલ્ય અપડેટ કરો, પછી રેન્જ પર એકીકૃત મૂલ્ય ક્વેરી કરો" ને ઝડપી બનાવે છે — સ્પર્ધી પ્રોગ્રામિંગ, વિશ્લેષણ વિંડોઝ અને અંતરાલ સમસ્યાઓ માટે જરૂરી છે।
તેમની વચ્ચે પસંદ કરવી એક ટ્રેડ-ઑફ છે: ફેનવિક ટ્રી સરવાળા માટે નાની અને ઝડપી છે, જ્યારે સેગમેન્ટ ટ્રી ન્યૂનતમ/મહત્તમ/રેન્જ-અપડેટ કાર્યોજ માટે વધુ લવચીક છે।