0Pricing
Competitive Programming Academy · Ders

Önek Toplamları için Fenwick Ağacı

Nokta güncellemesi ve log n'de önek sorgusu yapın.

Önek Toplamları için Fenwick Ağacı, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.

Önek Dizileri Neden İşe Yaramaz

Basit bir önek toplamı dizisi aralıkları anında yanıtlar; ancak tek bir güncelleme onu yeniden oluşturmanızı gerektirir. Çok sayıda güncelleme olduğunda bu işlem yavaşlar. ⏱️

Fenwick Ağacıyla Tanışın

Fenwick ağacı veya BIT, hem nokta güncellemelerini hem de önek sorgularını O(log n) zamanda destekler. Dinamik birikimli toplamlar için başvuracağınız yapı budur.

Tasarım Gereği Birden Başlayan İndeksleme

Fenwick ağacı, indekslemesi 1'den başlayan bir dizi içinde bulunur. 0 indeksini kullanılmayan bir işaretçi olarak ayırırız; böylece gerçek verileriniz 1. konumdan başlar.

tree = [0] * (n + 1)

En Düşük Ayarlı Bitin Sihri

Her indeks bir değerler bloğunu kapsar. Bloğun boyutu, i'nin en düşük ayarlı biti olan i & -i değerine eşittir. Tüm ağacın temelini bu küçük numara oluşturur.

lowbit = i & -i

Tek Bir Noktayı Güncelleme

i konumuna bir değer eklemek için her adımda en düşük biti kadar ileri atlarsınız ve i'yi içeren her bloğa dokunursunuz.

while i <= n:
    tree[i] += delta
    i += i & -i

Önek Toplamını Sorgulama

İlk i değeri toplamak için her adımda en düşük biti çıkararak sıfıra ulaşana kadar geriye doğru ilerlersiniz.

s = 0
while i > 0:
    s += tree[i]
    i -= i & -i

Her İki Döngü de Logaritmiktir

Her döngü, yineleme başına bir biti kapattığından en fazla log n kez çalışır. Bu nedenle hem güncelleme hem de sorgu hızlı kalır.

İki Önekten Aralık Toplamı

l ile r arasındaki toplamı mı istiyorsunuz? Statik bir önek dizisinde olduğu gibi prefix(r) eksi prefix(l-1) değerini alın; ancak artık güncellemeler de ucuzdur.

range_sum = query(r) - query(l - 1)

Ağacı Oluşturma

En basit oluşturma yöntemi, her başlangıç değeri için güncelleme çağırmaktır. Bu yöntem O(n log n) zamanda çalışır ve çoğu yarışma için yeterince hızlıdır.

for i, v in enumerate(a, 1):
    update(i, v)

Son Derece Küçük Bellek Kullanımı

Bir Fenwick ağacı yalnızca n+1 boyutunda tek bir diziye ihtiyaç duyar. Bu kompakt bellek kullanımı, yarışmalarda neden bu kadar sevildiğinin bir parçasıdır. 💾

BIT Ne Zaman Tercih Edilmeli

Nokta güncellemelerini önek veya aralık toplamı sorgularıyla dönüşümlü olarak kullanıyorsanız Fenwick ağacını seçin. Yazması kısadır ve geçilmesi zordur.

Hızlı Kontrol

Döngülerin nasıl ilerlediğini pekiştirelim.

Özet: BIT Temelleri

Fenwick ağacıyla tanıştınız: 1'den başlayan indeksleme, i & -i işlemiyle çalışma ve O(log n) zamanda nokta güncellemesi ile önek sorgusu. Sırada bunu ters sıralı çiftleri saymak için kullanacağız. 🎯

Sıkça Sorulan Sorular

“Önek Toplamları için Fenwick Ağacı” dersi ücretsiz mi?

Evet — “Önek Toplamları için Fenwick Ağacı” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.

“Önek Toplamları için Fenwick Ağacı” dersinde ne öğreneceğim?

Nokta güncellemesi ve log n'de önek sorgusu yapın. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.

“Önek Toplamları için Fenwick Ağacı” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

  1. Önek Toplamları için Fenwick Ağacı
  2. BIT ile Terslikler
  3. Segment Ağacı: Oluşturma ve Sorgulama
  4. Aralık Güncellemeleri için Tembel Yayılım
← Competitive Programming Academy Sayfasına Dön