0Pricing
Coding Interview Prep · Pelajaran

Propagasi Malas untuk Pembaruan Rentang

Menunda pembaruan pada seluruh rentang

Propagasi Malas untuk Pembaruan Rentang adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Masalah Pembaruan Rentang

Bagaimana jika kueri meminta Anda menambahkan 5 ke setiap elemen dari l hingga r? Menyentuh setiap daun memerlukan O(n) untuk setiap pembaruan, terlalu lambat jika ada banyak pembaruan rentang. 😰

Gagasan Penundaan

Propagasi tertunda memungkinkan sebuah simpul mengingat perubahan yang tertunda tanpa langsung meneruskannya ke anak-anak. Pekerjaan ditunda hingga Anda benar-benar memerlukan anak-anak tersebut.

Larik Kedua untuk Pekerjaan yang Tertunda

Bersama pohon, kita menyimpan larik penundaan. lazy[node] menyimpan pembaruan yang berlaku untuk seluruh rentang simpul tersebut, tetapi belum disalurkan ke bawah.

lazy = [0] * (4 * n)

Terapkan pada Seluruh Simpul

Ketika pembaruan mencakup seluruh simpul, sesuaikan nilai tersimpannya dan masukkan perubahan itu ke dalam larik penundaan, lalu berhenti. Anda tidak perlu turun ke anak-anaknya.

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

Salurkan ke Bawah Sebelum Turun

Sebelum mengunjungi anak-anak, salurkan ke bawah nilai penundaan apa pun yang tertunda ke keduanya. Dengan begitu, anak-anak tetap benar tepat ketika Anda membacanya.

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

Tiga Kasus untuk Setiap Simpul

Pada setiap simpul, rentang kueri dapat berupa saling terpisah, mencakup seluruhnya, atau sebagian. Lewati, terapkan secara tertunda, atau lakukan rekursi ke kedua paruh secara berturut-turut.

Pembaruan Tertunda Tetap Logaritmik

Pembaruan rentang hanya menyentuh O(log n) simpul karena simpul yang tercakup sepenuhnya berhenti lebih awal. Itulah seluruh manfaat pendekatan penundaan. ⚡

Kueri Rentang Juga Didorong ke Bawah

Kueri rentang juga harus didorong ke bawah sebelum melakukan rekursi agar membaca nilai anak yang terbaru. Lupa melakukan ini adalah kesalahan klasik pada propagasi malas.

Tarik ke Atas Setelah Rekursi

Setelah memperbarui anak-anak, gabungkan kembali simpul induk berdasarkan nilai anak-anak tersebut. Penarikan ke atas ini menjaga setiap simpul internal tetap konsisten dengan subpohonnya.

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

Penetapan vs Penjumlahan

Propagasi malas dapat digunakan untuk banyak operasi, tetapi penetapan dan penjumlahan digabungkan dengan cara yang berbeda. Tentukan cara menggabungkan dua pembaruan yang tertunda sebelum menulis kodenya.

Kapan Propagasi Malas Layak Digunakan

Gunakan propagasi malas hanya jika Anda benar-benar memerlukan pembaruan rentang. Untuk pembaruan titik saja, pohon segmen biasa lebih sederhana dan sudah memadai.

Uji Cepat

Apa yang harus dilakukan sebelum melakukan rekursi ke anak-anak sebuah simpul?

Rangkuman: Pembaruan Tertunda

Anda telah mempelajari propagasi malas: simpan perubahan yang tertunda, dorong ke bawah sebelum turun, tarik ke atas setelahnya, dan dapatkan pembaruan rentang dalam O(log n). 🎉

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Propagasi Malas untuk Pembaruan Rentang” gratis?

Ya — teks lengkap “Propagasi Malas untuk Pembaruan Rentang” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Propagasi Malas untuk Pembaruan Rentang”?

Menunda pembaruan pada seluruh rentang Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Propagasi Malas untuk Pembaruan Rentang” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Fenwick Tree untuk Jumlah Awalan
  2. Inversi dengan BIT
  3. Segment Tree: Membangun & Melakukan Query
  4. Propagasi Malas untuk Pembaruan Rentang
← Kembali ke Coding Interview Prep