Bir segment ağacı ve bir Fenwick ağacı (Binary Indexed Tree, BIT) hem aralık sorguları (ör. [l, r] üzerinde toplam) hem de nokta güncellemeleri O(log n) içinde yanıtlarken, saf bir tarama için O(n) veya ön ek toplamı dizisi için O(n) güncellemeleriyle karşılaştırılır.
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)
Bir segment ağacı, bir dizi segmentinin her biri için bir toplama değerini bir ikili ağaçta depolar ve herhangi bir ilişkisel işlemi (toplam, minimum, maksimum, gcd) ve tembel yayılımla aralık güncellemelerini de destekler.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Segment ağacı | |
|---|---|---|
| Sorgu / güncelleme | O(log n) | O(log n) |
| Alan | O(n) | O(2n) |
| İşlemler | toplamlar (tersinir) | herhangi bir ilişkisel işlem |
| Aralık güncellemeleri | daha zor | kolay (tembel yayılım) |
| Kod boyutu | küçük | daha büyük |
Bu yapılar "bir değeri güncelle, sonra bir aralık üzerinde bir toplamayı sorgula" hızlı hale getirir — rekabetçi programlama, analitik pencereleri ve aralık sorunları için gereklidir.
Aralarında seçim yapmak bir denge meselesidir: Fenwick ağacı toplamlar için küçük ve hızlı iken, segment ağacı minimum/maksimum/aralık güncellemesi iş yükleri için daha esnektir.
Junior'dan Senior'a detaylı cevaplarla bir BT mülakat soruları kütüphanesi.
Bağış Yap