Penyebaran Malas untuk Kemas Kini Julat
Tangguhkan kemas kini untuk seluruh julat.
Penyebaran Malas untuk Kemas Kini Julat ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Masalah Kemas Kini Julat
Bagaimana jika pertanyaan meminta anda menambah 5 kepada setiap elemen dari l hingga r? Menyentuh setiap daun mengambil O(n) bagi setiap kemas kini, terlalu perlahan untuk banyak kemas kini julat. 😰
Idea Tertunda
Penyebaran tertunda membolehkan nod mengingati perubahan yang menunggu tanpa menolaknya kepada anak-anak terlebih dahulu. Kerja itu ditangguhkan sehingga anda benar-benar memerlukan anak-anak tersebut.
Tatasusunan Kedua untuk Kerja Tertangguh
Di samping pepohon, kami menyimpan tatasusunan tertunda. Nilai tertunda bagi nod menyimpan kemas kini yang terpakai pada seluruh julat nod itu tetapi belum diturunkan.
lazy = [0] * (4 * n)Gunakan pada Seluruh Nod
Apabila kemas kini meliputi sesuatu nod sepenuhnya, laraskan nilainya yang disimpan dan simpan perubahan itu dalam tertunda, kemudian berhenti. Anda tidak perlu turun ke bawah.
seg[node] += (r - l + 1) * val
lazy[node] += valTurunkan Sebelum Menurun
Sebelum melawat anak-anak, turunkan sebarang nilai tertunda yang menunggu kepada kedua-duanya. Dengan cara ini, anak-anak sentiasa betul 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] = 0Tiga Kes bagi Setiap Nod
Pada setiap nod, julat pertanyaan adalah tidak bersilang, meliputi sepenuhnya, atau separa. Langkau, gunakan secara tertunda, atau ulang secara rekursif pada kedua-dua bahagian masing-masing.
Kemas Kini Tertunda Kekal Logaritma
Kemas kini julat hanya menyentuh O(log n) nod kerana nod yang diliputi sepenuhnya berhenti lebih awal. Itulah keseluruhan manfaat pendekatan tertunda. ⚡
Pertanyaan Juga Ditolak ke Bawah
Pertanyaan julat juga mesti ditolak ke bawah sebelum rekursi, supaya nilai anak yang terkini dibaca. Jika terlupa, inilah pepijat klasik bagi propagasi tertunda.
Tarik ke Atas Selepas Rekursi
Selepas mengemas kini anak, gabungkan semula nod induk berdasarkan anak-anaknya. Tarikan ke atas ini memastikan setiap nod dalaman konsisten dengan subpokoknya.
seg[node] = seg[2*node] + seg[2*node+1]Penetapan Berbanding Penambahan
Propagasi tertunda berfungsi untuk banyak operasi, tetapi penetapan dan penambahan digabungkan dengan cara yang berbeza. Tentukan cara dua kemas kini tertunda bergabung sebelum menulis kod.
Bila Propagasi Tertunda Berbaloi
Gunakan propagasi tertunda hanya apabila anda benar-benar memerlukan kemas kini julat. Untuk kemas kini titik sahaja, pokok segmen biasa lebih mudah dan sudah memadai.
Semakan Pantas
Apakah yang mesti dilakukan sebelum melakukan rekursi ke dalam anak-anak nod?
Rumusan: Kemas Kini Tertunda
Anda telah mempelajari propagasi tertunda: simpan perubahan tertunda, tolak ke bawah sebelum menurun, tarik ke atas selepas itu, dan dapatkan kemas kini julat dalam O(log n). 🎉
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Penyebaran Malas untuk Kemas Kini Julat” percuma?
Ya — teks penuh “Penyebaran Malas untuk Kemas Kini Julat” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Penyebaran Malas untuk Kemas Kini Julat”?
Tangguhkan kemas kini untuk seluruh julat. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Penyebaran Malas untuk Kemas Kini Julat” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Pepohon Fenwick untuk Jumlah Awalan
- Songsangan dengan BIT
- Pepohon Segmen: Bina dan Pertanyaan
- Penyebaran Malas untuk Kemas Kini Julat