Array Selisih untuk Pembaruan Rentang

Jumlah prefiks menjawab query rentang dengan cepat. Larik selisih membalik pendekatan ini untuk menerapkan banyak pembaruan rentang dengan cepat. 🔁

Menambahkan sebuah nilai ke setiap elemen dalam rentang, berulang kali, memerlukan O(n) untuk setiap pembaruan. Untuk q pembaruan, biayanya membengkak.

Alih-alih menyentuh setiap sel, catat hanya tempat perubahan dimulai dan tempat perubahan berakhir. Tandai tepinya, bukan bagian tengahnya.

Larik selisih menyimpan jarak antara setiap elemen dan elemen sebelumnya. Mengubah satu jarak dapat menggeser seluruh bagian setelahnya.

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.

Penambahan pada l mengaktifkan perubahan; pengurangan pada r + 1 menonaktifkannya kembali. Keduanya membatasi pembaruan pada satu rentang.

Setiap pembaruan hanya berupa dua penulisan ke larik, sehingga q pembaruan memerlukan total O(q). Pekerjaan beratnya ditunda hingga akhir.

Setelah semua penanda ditempatkan, hitung jumlah prefiks dari larik selisih. Satu lintasan itu merekonstruksi setiap nilai akhir.

Buat larik satu sel lebih panjang agar r + 1 tidak pernah melewati ujung. Slot pengaman tambahan ini mencegah kesalahan indeks.

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.

Larik selisih sangat berguna untuk jumlah pemesanan, tarif jalan, dan masalah apa pun dengan banyak operasi penambahan-rentang serta satu pembacaan akhir.

Anda menambahkan v ke setiap elemen dari indeks l hingga r.

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. ✅