Fenwick Tree (BIT)

#Nasıl çalışır?

Fenwick tree (ikili indeksli ağaç, Binary Indexed Tree), önek toplamlarını ve tek eleman güncellemelerini O(log n)'de yapan, segment tree'den çok daha az kodla yazılan bir yapıdır. Tüm yapı tek bir dizidir.

tree[i], a dizisinin i'de biten ve uzunluğu i & −i (i'nin en düşük 1 biti) olan parçasının toplamını tutar. Örneğin i = 6 (110₂) için i & −i = 2, yani tree[6] = a[5] + a[6].

Önek toplamı için i'den başlanır, tree[i] eklenir ve i'nin en düşük biti silinir (i -= i & −i); i sıfır olunca durulur. Bir elemana ekleme yaparken tersine en düşük bit eklenir (i += i & −i) ve bu konumu kapsayan tüm hücreler güncellenir. Her iki durumda da en fazla log n adım atılır.

#Kendin dene

#Temel işlemler

prefixSum(i)

a[1..i] toplamını O(log n) zamanda döndürür.

add(i, Δ)

a[i] değerine Δ ekler ve onu kapsayan hücreleri O(log n) zamanda günceller.

rangeSum(l, r)

prefixSum(r) − prefixSum(l − 1).

build(a)

Her elemanı tek tek ekleyerek O(n log n), ya da akıllıca O(n) zamanda kurar.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

class Fenwick:
    """tree[i] holds the sum of the i & -i elements ending at position i (1-based)."""

    def __init__(self, n: int) -> None:
        self.tree = [0] * (n + 1)

    def add(self, i: int, delta: int) -> None:
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i  # the next node that covers i

    def prefix_sum(self, i: int) -> int:
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i  # drop the lowest set bit
        return total

    def range_sum(self, l: int, r: int) -> int:
        return self.prefix_sum(r) - self.prefix_sum(l - 1)


a = [5, 2, 7, 3, 6, 1, 4, 8]
fw = Fenwick(len(a))
for i, v in enumerate(a, start=1):
    fw.add(i, v)

print(fw.prefix_sum(6))   # a[1..6]
fw.add(6, 3)
print(fw.prefix_sum(6))
print(fw.range_sum(3, 6))  # a[3..6]

#Karmaşıklık

i'nin ikili gösteriminde en fazla log n bit olduğu için her işlem en fazla log n adım sürer. Segment tree ile aynı karmaşıklıktadır ama sabitleri daha küçüktür ve kodu birkaç satırdır; buna karşılık en küçük/en büyük gibi tersi alınamayan işlemleri aralık için doğrudan desteklemez.

#Ne zaman kullanılır?

Frekans ve sayım tabloları, sıralı istatistikler (k. en küçük eleman), ters çevrim (inversion) sayımı, iki boyutlu önek toplamları ve sık güncellenen kümülatif toplamların gerektiği her yer.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.