0Pricing
Coding Interview Prep · 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 Coding Interview Prep 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep 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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep 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. Coding Interview Prep 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.

Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep 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
← Coding Interview Prep Sayfasına Dön