Fenwick ağacı (Binary Indexed Tree)

Kısaca: Fenwick ağacı, bir sayı dizisini öyle saklar ki hem bir değeri güncellemek hem de önek toplamları O(log n)‘de mümkün olur.

Biraz daha ayrıntılı: Yalnızca toplamlar (veya benzer tersinir işlemler) gerektiğinde segment ağacına özellikle kompakt bir alternatiftir. Ağaç düz bir dizide yaşar ve indeks hesabı en düşük kurulu biti kullanır.

Ayrıntılı

• Fikir: i konumu, uzunluğu i’yi bölen en büyük ikinin kuvvetine eşit olan bir kesitin toplamını saklar.
• Sorgu: i’ye kadar önek toplamı: değeri ekle, sonra i 0 olana dek i -= i & -i.
• Güncelleme: Bir değeri d kadar değiştir: i’de ekle, sonra i boyutu aşana dek i += i & -i.
• Aralık toplamı: toplam(r) - toplam(l-1).
• Kuruluş: O(n)‘de mümkün, bellek yalnızca n sayı.
• Sınırlar: Her işlem tersinir değildir. Aralık minimumu bu yüzden genellikle segment ağacı gerektirir.

Ayrıca bak: Büyük-O gösterimi