Segment Tree

#Nasıl çalışır?

Segment tree (aralık ağacı), bir dizinin aralıkları üzerinde toplam, en küçük ya da en büyük gibi sorguları hızla cevaplayan ve diziyi değiştirmeye de izin veren bir ikili ağaçtır.

Kök tüm diziyi, iki çocuğu dizinin iki yarısını, onların çocukları dörtte birlerini kapsar; yapraklar tek tek elemanlardır. Her düğüm kendi aralığının toplamını tutar.

Bir a[l..r] sorgusunda tamamen içeride kalan bir düğümün toplamı doğrudan alınır, tamamen dışarıdaki bir düğüm atlanır, yalnızca kısmen örtüşen düğümlerin çocuklarına inilir. Böylece her sorgu en fazla yaklaşık 2·log n düğümle cevaplanır.

Bir eleman değişince yalnızca o yapraktan köke giden yoldaki düğümler yeniden hesaplanır.

#Kendin dene

#Temel işlemler

query(l, r)

a[l..r] aralığının toplamını O(log n) zamanda döndürür.

update(i, x)

a[i] = x yapar ve yoldaki toplamları O(log n) zamanda günceller.

build(a)

Ağacı alttan yukarı O(n) zamanda kurar.

Tembel yayılım (lazy propagation)

Bir aralığın tamamına ekleme gibi güncellemeleri de O(log n)'de yapmayı sağlayan genişletme.

#Örnek kod

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

class SegmentTree:
    """Range sums with point updates; node k covers a range, its children are 2k and 2k + 1."""

    def __init__(self, a: list) -> None:
        self.n = len(a)
        self.sums = [0] * (4 * self.n)
        self._build(1, 0, self.n - 1, a)

    def _build(self, k: int, lo: int, hi: int, a: list) -> None:
        if lo == hi:
            self.sums[k] = a[lo]
            return
        mid = (lo + hi) // 2
        self._build(2 * k, lo, mid, a)
        self._build(2 * k + 1, mid + 1, hi, a)
        self.sums[k] = self.sums[2 * k] + self.sums[2 * k + 1]

    def query(self, l: int, r: int, k: int = 1, lo: int = 0, hi: int = -1) -> int:
        if hi == -1:
            hi = self.n - 1
        if r < lo or hi < l:      # completely outside
            return 0
        if l <= lo and hi <= r:   # completely inside
            return self.sums[k]
        mid = (lo + hi) // 2      # partly: ask both children
        return self.query(l, r, 2 * k, lo, mid) + self.query(l, r, 2 * k + 1, mid + 1, hi)

    def update(self, i: int, x: int, k: int = 1, lo: int = 0, hi: int = -1) -> None:
        if hi == -1:
            hi = self.n - 1
        if lo == hi:
            self.sums[k] = x
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self.update(i, x, 2 * k, lo, mid)
        else:
            self.update(i, x, 2 * k + 1, mid + 1, hi)
        self.sums[k] = self.sums[2 * k] + self.sums[2 * k + 1]


tree = SegmentTree([5, 2, 7, 3, 6, 1, 4, 8])
print(tree.query(2, 5))  # 7 + 3 + 6 + 1
tree.update(5, 10)
print(tree.query(2, 5))  # 7 + 3 + 6 + 10

#Karmaşıklık

Basit bir önek toplamı dizisi sorguyu O(1)'de cevaplar ama her güncellemede O(n) yeniden hesaplama ister. Segment tree ikisini de O(log n)'de yapar. Toplam yerine en küçük, en büyük, EBOB gibi birleşmeli (associative) her işlem kullanılabilir.

#Ne zaman kullanılır?

Hem sorgu hem güncelleme içeren aralık problemleri: canlı skor tabloları, zaman serilerinde aralık en büyüğü, oyunlarda bölge sorguları, hesaplamalı geometride tarama çizgisi algoritmaları ve yarışma programlamanın klasik problemleri.

#Alıştırma

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

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Fenwick Tree (BIT)