Array Selisih untuk Pembaruan Rentang
Menerapkan banyak operasi penambahan rentang dengan cepat
Array Selisih 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.
Balik Permasalahannya
Jumlah prefiks menjawab query rentang dengan cepat. Larik selisih membalik pendekatan ini untuk menerapkan banyak pembaruan rentang dengan cepat. 🔁
Cara yang Lambat
Menambahkan sebuah nilai ke setiap elemen dalam rentang, berulang kali, memerlukan O(n) untuk setiap pembaruan. Untuk q pembaruan, biayanya membengkak.
Simpan Perubahannya
Alih-alih menyentuh setiap sel, catat hanya tempat perubahan dimulai dan tempat perubahan berakhir. Tandai tepinya, bukan bagian tengahnya.
Isi Larik Selisih
Larik selisih menyimpan jarak antara setiap elemen dan elemen sebelumnya. Mengubah satu jarak dapat menggeser seluruh bagian setelahnya.
Trik Dua Penanda
Untuk menambahkan v dari l hingga r, tambahkan v pada indeks l dan kurangi v pada indeks r + 1. Hanya dua perubahan yang mencakup seluruh rentang.
diff[l] += v
diff[r + 1] -= vMengapa Ada Pengurangan
Penambahan pada l mengaktifkan perubahan; pengurangan pada r + 1 menonaktifkannya kembali. Keduanya membatasi pembaruan pada satu rentang.
Terapkan Semua Pembaruan dengan Murah
Setiap pembaruan hanya berupa dua penulisan ke larik, sehingga q pembaruan memerlukan total O(q). Pekerjaan beratnya ditunda hingga akhir.
Pulihkan Larik Akhir
Setelah semua penanda ditempatkan, hitung jumlah prefiks dari larik selisih. Satu lintasan itu merekonstruksi setiap nilai akhir.
for i in range(1, n):
diff[i] += diff[i - 1]Tentukan Ukuran dengan Slot Pengaman
Buat larik satu sel lebih panjang agar r + 1 tidak pernah melewati ujung. Slot pengaman tambahan ini mencegah kesalahan indeks.
Total Biaya
Anda menghabiskan O(q) untuk menandai pembaruan dan satu lintasan O(n) untuk membangun ulang. Biaya gabungannya jauh lebih kecil daripada O(n kali q) yang naif.
Di Mana Ini Unggul
Larik selisih sangat berguna untuk jumlah pemesanan, tarif jalan, dan masalah apa pun dengan banyak operasi penambahan-rentang serta satu pembacaan akhir.
Pemeriksaan Cepat
Anda menambahkan v ke setiap elemen dari indeks l hingga r.
Ringkasan
Anda dapat memproses pembaruan rentang secara berkelompok dengan larik selisih: tandai l dan r + 1, lalu hitung jumlah prefiks sekali untuk membangun ulang. Pembaruan cepat, satu pembacaan. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Array Selisih untuk Pembaruan Rentang” gratis?
Ya — teks lengkap “Array Selisih 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 “Array Selisih untuk Pembaruan Rentang”?
Menerapkan banyak operasi penambahan rentang dengan cepat 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 “Array Selisih 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
- Membangun Array Jumlah Awalan
- Menjumlahkan Rentang Apa Pun dengan Pengurangan
- Menghitung Subarray dengan Jumlah Target
- Array Selisih untuk Pembaruan Rentang