სეგმენტის ხე და ფენვიკის ხე (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) და, lazy propagation-ის გამოყენებით, დიაპაზონის განახლებებსაც.
[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) |
| კოდის ზომა | ძალიან მცირე | უფრო დიდი |
ეს სტრუქტურები აქცევენ "ოდენობის განახლება, შემდეგ აგრეგატის მოთხოვნა დიაპაზონზე" სწრაფ ოპერაციას — აუცილებელი კონკურენტული პროგრამირებისთვის, ანალიტიკის ფანჯრებისთვის და ინტერვალის პრობლემებისთვის.
იმის არჩევა მათ შორის არის გადახდი: ფენვიკის ხე მცირე და სწრაფია ჯამებისთვის, ხოლო სეგმენტის ხე უფრო მოქნილია მინ/მაქს/დიაპაზონის განახლების დატვირთვისთვის.