Aralık ve Fenwick Ağaçları

Bir ölçüm dizisinde şu iki işlem art arda yapılsın: belirli bir aralıktaki değerlerin toplamını sor, ve tek bir değeri güncelle. İkisi de sık yapılıyorsa, buraya kadarki yapıların hiçbiri iyi bir yanıt vermez.

İki Uç Çözüm

Ham dizi. Güncelleme tek bir yazmadır: $O(1)$. Aralık toplamı ise aralıktaki tüm elemanları gezer: $O(n)$.

Ön ek toplamı dizisi. Baştan itibaren biriken toplamlar önceden hesaplanırsa, herhangi bir aralığın toplamı iki değerin farkıdır: $O(1)$. Buna karşılık tek bir değer değiştiğinde, ondan sonraki tüm ön ek toplamları yeniden hesaplanmalıdır: $O(n)$.

olcumler = [12, 18, 7, 25, 14, 30]

on_ek = [0] * (len(olcumler) + 1)
for i, deger in enumerate(olcumler):
    on_ek[i + 1] = on_ek[i] + deger

print(on_ek)                      # [0, 12, 30, 37, 62, 76, 106]
print(on_ek[4] - on_ek[1])        # 50   — 1..3 aralığı: 18 + 7 + 25

İki çözüm de bir işlemi sabit, diğerini doğrusal yapar. Her ikisi de sık yapılıyorsa ikisi de yetersizdir; aranan, her ikisini birden logaritmik yapan bir yapıdır.

Aralık Ağacı

Aralık ağacı (segment tree), diziyi ikili olarak böler: kök tüm diziyi, çocukları yarılarını, onların çocukları çeyreklerini temsil eder. Her düğüm, kendi aralığının özetini — burada toplamını — saklar.

                [0..5] = 106
             /                \
        [0..2] = 37        [3..5] = 69
        /      \            /       \
   [0..1]=30  [2..2]=7  [3..4]=39  [5..5]=30
    /    \                 /   \
 [0]=12 [1]=18         [3]=25 [4]=14

Sorgu, istenen aralığı ağaçtaki düğümlerin birleşimi olarak yazar. Herhangi bir aralık, en fazla $O(\log n)$ düğümle kaplanabilir; bu, sorgu maliyetinin kaynağıdır.

Güncelleme, ilgili yaprağı değiştirir ve kökten yaprağa giden yol üzerindeki tüm özetleri yeniden hesaplar — yine $O(\log n)$.

class AralikAgaci:
    """Toplam sorgusu ve nokta güncellemesi; ikisi de O(log n)."""

    def __init__(self, veri: list[int]) -> None:
        self._n = len(veri)
        self._agac = [0] * (2 * self._n)         # yapraklar ikinci yarıda
        for i, deger in enumerate(veri):
            self._agac[self._n + i] = deger
        for i in range(self._n - 1, 0, -1):      # iç düğümler alttan yukarı
            self._agac[i] = self._agac[2 * i] + self._agac[2 * i + 1]

    def guncelle(self, dizin: int, deger: int) -> None:
        i = self._n + dizin
        self._agac[i] = deger
        i //= 2
        while i >= 1:                            # köke kadar özetleri tazele
            self._agac[i] = self._agac[2 * i] + self._agac[2 * i + 1]
            i //= 2

    def toplam(self, sol: int, sag: int) -> int:
        """[sol, sag) yarı açık aralığının toplamı."""
        sonuc = 0
        l, r = self._n + sol, self._n + sag
        while l < r:
            if l % 2 == 1:                       # sol sınır sağ çocuksa al
                sonuc += self._agac[l]
                l += 1
            if r % 2 == 1:                       # sağ sınır sağ çocuksa al
                r -= 1
                sonuc += self._agac[r]
            l //= 2
            r //= 2
        return sonuc


agac = AralikAgaci([12, 18, 7, 25, 14, 30])
print(agac.toplam(0, 6))          # 106  — tüm dizi
print(agac.toplam(1, 4))          # 50   — 18 + 7 + 25
agac.guncelle(2, 100)             # 7 yerine 100
print(agac.toplam(1, 4))          # 143
print(agac.toplam(0, 6))          # 199

Yapının genelliği dikkat çekicidir: birleştirme işlemi toplama yerine en büyük, en küçük, en büyük ortak bölen veya birleşme özelliği olan herhangi bir işlem olabilir. Yalnızca düğümlerde saklanan özet ile birleştirme satırı değişir.

Fenwick Ağacı

Fenwick ağacı (ikili dizinli ağaç), yalnızca ön ek toplamlarıyla ilgilenen daha kompakt bir yapıdır. Aynı işi $n$ gözlük tek bir diziyle yapar; aralık ağacının yarısı kadar bellek kullanır ve kodu belirgin biçimde kısadır.

Fikri, her dizinin belirli bir aralığın toplamını saklamasıdır ve bu aralığın uzunluğu, dizinin ikilik gösterimindeki en düşük kurulu bitle belirlenir. Bilgisayarlar Nasıl Çalışır kursundaki x & -x deyimi burada doğrudan kullanılır.

class FenwickAgaci:
    """Ön ek toplamı ve nokta güncellemesi; O(log n)."""

    def __init__(self, boyut: int) -> None:
        self._agac = [0] * (boyut + 1)           # 1 tabanlı dizin

    def ekle(self, dizin: int, artis: int) -> None:
        i = dizin + 1
        while i < len(self._agac):
            self._agac[i] += artis
            i += i & -i                          # bir sonraki sorumlu dizin

    def on_ek(self, dizin: int) -> int:
        """[0, dizin) aralığının toplamı."""
        sonuc, i = 0, dizin
        while i > 0:
            sonuc += self._agac[i]
            i -= i & -i                          # en düşük kurulu biti düşür
        return sonuc

    def aralik(self, sol: int, sag: int) -> int:
        return self.on_ek(sag) - self.on_ek(sol)


f = FenwickAgaci(6)
for i, deger in enumerate([12, 18, 7, 25, 14, 30]):
    f.ekle(i, deger)

print(f.on_ek(6))            # 106
print(f.aralik(1, 4))        # 50
f.ekle(2, 93)                # 7 + 93 = 100
print(f.aralik(1, 4))        # 143

Fenwick ağacı güncellemeyi artış olarak alır; bir değeri doğrudan belirlemek için eski değerle farkı eklenir. Bu, yapının ön ek toplamı odaklı tasarımının bir sonucudur.

Hangi Yapı Ne Zaman

Yapı	Aralık sorgusu	Nokta güncellemesi	Bellek	Genellik
Ham dizi	$O(n)$	$O(1)$	$n$	Tam
Ön ek toplamı	$O(1)$	$O(n)$	$n$	Yalnız toplama
Aralık ağacı	$O(\log n)$	$O(\log n)$	$2n$	Birleşmeli her işlem
Fenwick ağacı	$O(\log n)$	$O(\log n)$	$n$	Toplama ve tersi olan işlemler

Seçim ölçütleri:

• Veri değişmiyorsa ön ek toplamı en iyisidir; ek yapı gereksizdir.
• Yalnızca toplam sorgulanıyorsa Fenwick yeterlidir: daha az bellek, daha kısa kod.
• En küçük/en büyük gibi tersi olmayan işlemler veya aralık güncellemesi gerekiyorsa aralık ağacı kullanılır.

Aralık ağacının bir uzantısı, aralık güncellemelerini de logaritmik yapar: güncelleme hemen alta yayılmaz, düğümde bir “bekleyen değişiklik” olarak tutulur ve ancak o alt ağaca inildiğinde uygulanır. Bu teknik, ileri algoritma konularında ele alınır.

Kullanım Alanları

Aralık sorguları, zaman serisi ve sıralı veri üzerinde çalışan sistemlerin ortak ihtiyacıdır: bir zaman aralığındaki ölçümlerin toplamı veya en büyüğü, sıralamada belirli bir aralıktaki kayıt sayısı, oyun dünyasında bir bölgedeki nesnelerin sayımı.

Veri değişmiyorsa aynı sorular önceden hesaplanmış özetlerle yanıtlanır; bu yapıların varlık nedeni, verinin değişmeye devam etmesidir.

Özet

• Ham dizi güncellemeyi, ön ek toplamı sorguyu sabit yapar; ikisi birden sık gerekiyorsa ikisi de yetersizdir.
• Aralık ağacı diziyi ikili böler ve her düğümde alt aralığın özetini saklar; sorgu ve güncelleme $O(\log n)$’dir.
• Herhangi bir aralık, en fazla logaritmik sayıda düğümle kaplanır.
• Birleştirme işlemi değiştirilerek aynı yapı en küçük, en büyük veya başka birleşmeli işlemler için kullanılır.
• Fenwick ağacı yalnızca ön ek toplamlarıyla ilgilenir; yarı bellek ve daha kısa kodla aynı maliyeti verir.
• Yapıların varlık nedeni verinin değişmesidir; sabit veride önceden hesaplanmış özetler yeterlidir.

Sonraki Adım

Aralık sorguları tek boyutluydu: dizinler bir çizgi üzerinde. Konum verisi iki veya daha çok boyutluysa — harita üzerindeki noktalar, öznitelik uzayındaki kayıtlar — bölme fikri nasıl genişletilir? Sonraki ders, bu konunun son yapısı olan çok boyutlu ağaçları ele alacak.