0Pricing
Competitive Programming Academy · Ders

Aralık Güncellemeleri için Tembel Yayılım

Güncellemeleri tüm aralıklarda erteleyin.

Aralık Güncellemeleri için Tembel Yayılım, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 4. 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.

Aralık Güncelleme Sorunu

Bir sorgu l ile r arasındaki her öğeye 5 eklemenizi isterse ne olur? Her yaprağa dokunmak, güncelleme başına O(n) zaman alır; çok sayıda aralık güncellemesi için bu çok yavaştır. 😰

Erteleme Fikri

Tembel yayma, bir düğümün bekleyen bir değişikliği henüz çocuklarına aktarmadan hatırlamasını sağlar. İşlem, çocuklara gerçekten ihtiyaç duyana kadar ertelenir.

Bekleyen İşlemler İçin İkinci Dizi

Ağacın yanında bir erteleme dizisi tutarız. lazy[node], o düğümün tüm aralığına uygulanacak ancak henüz aşağı aktarılmamış bir güncellemeyi saklar.

lazy = [0] * (4 * n)

Tüm Düğüme Uygulama

Bir güncelleme bir düğümü tamamen kapsadığında, düğümde saklanan değeri ayarlayın ve değişikliği lazy içine ekleyin, sonra durun. Alt düğümlere inmeye gerek yoktur.

seg[node] += (r - l + 1) * val
lazy[node] += val

Aşağı İnmeden Önce Aşağı Aktarma

Çocukları ziyaret etmeden önce bekleyen tembel değeri her iki çocuğa da aşağı aktarın. Böylece çocuklar tam da okuduğunuz anda doğru durumda olur.

def push_down(node, l, r):
    if lazy[node]:
        apply(2*node, l, mid)
        apply(2*node+1, mid+1, r)
        lazy[node] = 0

Düğüm Başına Üç Durum

Her düğümde sorgu aralığı ayrık, tamamen kapsanmış veya kısmi durumdadır. Sırasıyla atlayın, erteleyerek uygulayın veya her iki yarıda özyinelemeli olarak ilerleyin.

Tembel Güncellemeler Logaritmik Kalır

Bir aralık güncellemesi yalnızca O(log n) düğüme dokunur; çünkü tamamen kapsanan düğümlerde işlem erkenden sona erer. Tembel yaklaşımın tüm kazancı budur. ⚡

Sorguları da Aşağı Yayın

Aralık sorguları da özyinelemeye geçmeden önce aşağı yayılmalıdır; böylece alt düğümlerin güncel değerlerini okurlar. Bunu unutmak, ertelenmiş yayılımın klasik hatasıdır.

Özyinelemeden Sonra Yukarı Toplayın

Alt düğümleri güncelledikten sonra, üst düğümü onlardan yeniden oluşturun. Bu yukarı toplama, her iç düğümün alt ağacıyla tutarlı kalmasını sağlar.

seg[node] = seg[2*node] + seg[2*node+1]

Atama ve Toplama

Ertelenmiş yayılım birçok işlemde işe yarar, ancak atama ile toplama farklı biçimde birleştirilir. Kodlamadan önce bekleyen iki güncellemenin nasıl birleştirileceğine karar verin.

Ertelenmiş Yayılım Ne Zaman Değerlidir

Ertelenmiş yayılıma yalnızca gerçekten aralık güncellemelerine ihtiyaç duyduğunuzda başvurun. Yalnızca nokta güncellemeleri için basit bir segment ağacı daha kolaydır ve yeterlidir.

Hızlı Kontrol

Bir düğümün alt düğümlerine özyinelemeyle geçmeden önce ne yapılmalıdır?

Özet: Ertelenmiş Güncellemeler

Ertelenmiş yayılımı öğrendiniz: bekleyen değişiklikleri saklayın, aşağı inerken aşağı yayın, dönüşte yukarı toplayın ve O(log n) aralık güncellemeleri elde edin. 🎉

Sıkça Sorulan Sorular

“Aralık Güncellemeleri için Tembel Yayılım” dersi ücretsiz mi?

Evet — “Aralık Güncellemeleri için Tembel Yayılım” 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.

“Aralık Güncellemeleri için Tembel Yayılım” dersinde ne öğreneceğim?

Güncellemeleri tüm aralıklarda erteleyin. 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 4. dersidir.

“Aralık Güncellemeleri için Tembel Yayılım” 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