Segment Ağacı: Oluşturma ve Sorgulama
Aralık minimumunu, maksimumunu veya toplamını log n'de bulun.
Segment Ağacı: Oluşturma ve Sorgulama, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. 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.
Fenwick Ağacının Ötesinde
Fenwick ağacı toplamlar için mükemmeldir; ancak bir aralık ağacı minimum, maksimum, gcd ve daha fazlasını işler. Aralık sorgularının esnek işçisidir.
Aralıklar Üzerinde Bir Ağaç
Her düğüm dizinin bir aralığına sahiptir. Kök her şeyi kapsar; çocuklar, yapraklar tek bir öğe tutana kadar aralığı ikiye böler.
Dizi Tabanlı Depolama
Ağacı 2n veya 4n boyutundaki düz bir dizide tutarız. 1 numaralı düğüm köktür; i düğümünün çocukları 2i ve 2i+1 konumlarında bulunur.
seg = [0] * (2 * n)Yapraklar Verileri Tutar
Yinelemeli biçimde, özgün değerler dizinin ikinci yarısında, n ile 2n-1 arasındaki indekslerde bulunur.
for i in range(n):
seg[n + i] = a[i]Aşağıdan Yukarıya Oluşturma
Her iç düğüm, iki çocuğunun combine işleminden elde edilir. Onları n-1'den 1'e doğru doldurun; tüm ağaç hazır olur.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]Combine İşlemi
combine işlevi ağacı tanımlar. Toplamlar için toplama, minimumlar için min veya maksimumlar için max kullanın. Sorguyu değiştirmek için bu işlemi değiştirin.
def combine(x, y):
return min(x, y)Nokta Güncelleme, Ardından Yukarı Çıkma
Tek bir değeri değiştirmek için yaprağı ayarlayın ve köke doğru ilerleyerek yol üzerindeki her ebeveyni iki çocuğundan yeniden hesaplayın.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Yarı Açık Aralığı Sorgulama
Aralık sorguları her iki uçtan tarama yaparak sınır düğümlerini yanıta katar. Aralık yarı açıktır; l konumundan başlayıp r konumuna kadar gelir, ancak r'yi kapsamaz.
Yinelemeli Sorgu Döngüsü
l ve r'yi birbirine doğru ilerletin. Bir indeks tek bir sınır olduğunda, işaretçiyi ilerletmeden önce o düğümü yanıta katın.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2Her İki Uçta da Logaritmik
Oluşturma O(n) zamanda, her güncelleme ve sorgu ise O(log n) zamanda çalışır. Aralık ağaçlarını bu kadar kullanışlı kılan denge budur.
Etkisiz Elemanı Unutmayın
Sonucunuzu işlemin etkisiz elemanıyla başlatın: toplam için 0, minimum için sonsuz, maksimum için negatif sonsuz. Yanlış başlangıç yanlış sonuç verir.
res = float('inf')Hızlı Kontrol
Yinelemeli ağaçta ham veriler nerede bulunur?
Özet: Esnek Aralıklar
Bir aralık ağacı oluşturdunuz: yapraklar ikinci yarıda, ebeveynler combine sonuçları olarak bulunur ve toplam, minimum veya maksimum için güncellemeler ve sorgular O(log n) zamanda yapılır. 🌳
Sıkça Sorulan Sorular
“Segment Ağacı: Oluşturma ve Sorgulama” dersi ücretsiz mi?
Evet — “Segment Ağacı: Oluşturma ve Sorgulama” 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.
“Segment Ağacı: Oluşturma ve Sorgulama” dersinde ne öğreneceğim?
Aralık minimumunu, maksimumunu veya toplamını log n'de bulun. 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 3. dersidir.
“Segment Ağacı: Oluşturma ve Sorgulama” 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
- Önek Toplamları için Fenwick Ağacı
- BIT ile Terslikler
- Segment Ağacı: Oluşturma ve Sorgulama
- Aralık Güncellemeleri için Tembel Yayılım