Prefix, Fenwick, segment tree ve sparse table

Statik prefix toplamı sum(l,r)=P[r]−P[l] ile O(1) sorgu verir; tek öğe değişince birçok prefix güncellenir. Fenwick tree düşük anlamlı1 biti üzerinden belirli prefix bloklarını saklar. Add ve prefix sum O(log n); aralık toplamı iki prefix farkıdır.

Segment tree aralığı ikiye bölerek aggregate saklar. Combine işlemi associative olmalı; identity boş aralığı temsil eder. Sum/min/max/gcd gibi farklı monoid'ler kullanılabilir. Lazy propagation toplu range update'i etikette erteler; tag composition sırası özellikle assignment ve addition birlikteyse önemlidir. Push etmeden çocuk okumak stale sonuç üretir.

Sparse table statik idempotent işlemlerde (örneğin min) iki örtüşen blokla O(1) sorgu verir; sum için aynı örtüşme iki sayma yaratır. Fenwick genel min güncellemesini sum kadar kolay desteklemez; ters işlemin olup olmadığını düşün. Bu yapıların hepsi “her aralığı her işlemle log n” diye genellenemez.

Hangi aralık yapısı, hangi cebir?

Prefix sum'da prefix[i+1]=prefix[i]+a[i]. [l,r) toplamı prefix[r]−prefix[l] olur. Update tek elemanı değiştirince sonraki bütün prefix'ler etkilenir. Fenwick, lowbit(i)=i&−i ile power-of-two uzunluklu alt aralıklar tutar; update yukarı, prefix query aşağı atlar. Kodda dış API zero-based, iç indeks one-based olabilir; bu dönüşümü test et.

Segment tree birleştirme işleminin associative olmasını ister. Sum için identity 0, min için +∞, max için −∞. İşlemin commutative olması zorunlu değildir; string concatenation segment tree'sinde query parçalarının sırası korunmalıdır. [l,r) ile inclusive [l,r] sözleşmesini karıştırmak off-by-one hatasının ana kaynağıdır.

Lazy propagation'da node aggregate güncellenir ve pending tag çocuklara ertelenir. Range add + range sum için segment uzunluğu gerekir: aggregate += delta·length. Range assign ile range add birlikte varsa tag composition sırası önemlidir; assign sonra add, add sonra assign ile aynı değildir.

Temel: [2,4,1,7] için prefix ve [1,3) toplamını çıkar. Orta: Fenwick update sonrası random query'leri naive sum ile karşılaştır. İleri: Range assign/add tag algebra'sını kur; identity, composition ve aggregate action yasalarını test et.

class Fenwick:
    def __init__(self, n): self.t = [0]*(n+1)
    def add(self, i, delta):
        if not 0 <= i < len(self.t)-1: raise IndexError(i)
        i += 1
        while i < len(self.t): self.t[i] += delta; i += i & -i
    def prefix(self, end):
        if not 0 <= end <= len(self.t)-1: raise IndexError(end)
        s = 0
        while end: s += self.t[end]; end -= end & -end
        return s
f = Fenwick(4)
for i,x in enumerate([2,1,3,4]): f.add(i,x)
assert f.prefix(3)-f.prefix(1) == 4