Tatasusunan Perbezaan untuk Kemas Kini Julat

Jumlah awalan menjawab pertanyaan julat dengan pantas. Tatasusunan beza pula membolehkan banyak kemas kini julat dilakukan dengan pantas. 🔁

Menambah nilai pada setiap elemen dalam julat, berulang kali, memerlukan O(n) bagi setiap kemas kini. Bagi q kemas kini, kos itu meningkat dengan mendadak.

Daripada menyentuh setiap sel, catat hanya tempat perubahan bermula dan tempat perubahan berakhir. Tandakan tepi, bukan bahagian tengah.

Tatasusunan beza menyimpan jarak antara setiap elemen dengan elemen sebelumnya. Mengubah satu jarak akan mengalihkan keseluruhan bahagian selepasnya.

Untuk menambah v dari l hingga r, tambah v pada indeks l dan tolak v pada indeks r + 1. Hanya dua perubahan meliputi seluruh julat.

Tanda tambah pada l menghidupkan perubahan; tanda tolak pada r + 1 mematikannya semula. Kedua-duanya mengehadkan kemas kini kepada satu julat.

Setiap kemas kini hanyalah dua penulisan tatasusunan, jadi q kemas kini mengambil O(q) secara keseluruhan. Kerja berat ditangguhkan hingga akhir.

Selepas semua tanda diletakkan, ambil jumlah awalan bagi tatasusunan beza. Satu laluan itu membina semula setiap nilai akhir.

Jadikan tatasusunan itu lebih panjang satu sel supaya r + 1 tidak pernah melepasi hujung. Sel pengawal tambahan ini mengelakkan ralat indeks.

Anda menggunakan O(q) untuk menandakan kemas kini dan satu laluan O(n) untuk membina semula. Kos gabungan itu jauh lebih rendah daripada O(n darab q) secara naif.

Tatasusunan beza sangat berguna untuk kiraan tempahan, tol jalan raya dan sebarang masalah dengan banyak operasi tambah-julat serta satu pembacaan akhir.

Anda boleh mengumpulkan kemas kini julat menggunakan tatasusunan beza: tandakan l dan r + 1, kemudian ambil jumlah awalan sekali untuk membina semula. Kemas kini pantas, satu pembacaan. ✅