Perkenalan tentang penanganan range update dengan lazy propagation pernah saya bahas di tulisan yang lalu. Pada tulisan ini, kita akan fokus ke implementasinya.
Konsep
Lazy propagation dapat diimplementasikan ketika:- Apabila seluruh elemen yang dicakupi sebuah segmen mendapatkan update, maka update harus disangkutkan pada segmen tersebut dengan efisien & tanpa menyentuh anak-anaknya.
- Apabila seluruh elemen yang dicakupi suatu segmen diperlukan dalam query, maka informasi asli dari segmen itu harus bisa didapatkan dengan efisien & tanpa menyentuh anak-anaknya.
Untuk keperluan penjelasan, nilai yang disangkutkan akan saya sebut "nilai lazy".
Penjelasan tentang cara implementasi akan dijelaskan melalui studi kasus 1 pada bagian selanjutnya. Kita juga akan mengambil abstraksi kode lazy propagation dari sana, untuk diterapkan pada studi kasus seterusnya.