---
title: 'Aralık ve Fenwick Ağaçları'
source: 'https://academia.sh/tr/kurslar/veri-yapilari/aralik-agaclari'
course: 'Veri Yapıları'
language: tr
updated: '2026-08-17T18:08:03+00:00'
license: 'CC BY-SA 4.0'
---

# Aralık ve Fenwick Ağaçları

Aralık sorgusu ile nokta güncellemesinin birlikte gerektiği durumlar, aralık ağacı ve Fenwick ağacı.

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)$.

```python
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)$.

```python
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.

```python
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.