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.
Studi Kasus 1: HORRIBLE (SPOJ)
Rasanya soal ini sangat sering dibahas...Soal lengkap dapat dilihat di https://www.spoj.com/problems/HORRIBLE.
Mari kita implementasikan fungsi update, yaitu menambahkan suatu nilai kepada suatu rentang.
Selain menyimpan nilai jumlahan pada setiap segmen, kita perlu menyimpan informasi nilai yang disangkutkan. Nilai ini secara intuitif terpikir adalah nilai yang seharusnya ditambahkan pada masing-masing elemen pada segmen tersebut. Mari kita sebut nilai itu "delayedAdd".
Kini segment tree kita perlu menyimpan dua nilai, yaitu jumlahan setiap segmen dan delayedAdd. Implementasinya dapat memanfaatkan struct:
Catatan: jangan lupa untuk menginisialisasi nilai sum dan delayedAdd dengan nilai 0.
Setiap kali setiap elemen yang dicakupi suatu segmen perlu mendapatkan tambahan nilai, kita tambahkan nilai lazy "delayedAdd" dengan nilai tersebut.
Nah untuk kasus update yang tidak dilakukan pada seluruh elemen pada segmen, kita perlu turun ke anak-anak segmen itu secara rekursif (seperti range query biasanya). Namun ketika segmen ini memiliki nilai lazy, kita harus melanjutkan pekerjaan yang tertunda itu. Caranya:
- Menurunkan nilai lazy dari segmen itu ke anak-anaknya, sehingga segmen itu sudah tidak lagi menyimpan nilai lazy. Bayangkan seperti pekerjaan di segmen tersebut yang tertunda sudah selesai dilaksanakan. Tahap ini sering disebut "propagate".
- Lanjut melakukan range update pada anaknya yang bersangkutan.
- Saat range update anak-anak selesai dilakukan, perbaharui nilai segmen dengan memanfaatkan informasi dari anak-anaknya (seperti tahap "MERGE" yang diperkenalkan tulisan sebelumnya).
Penting untuk disadari bahwa sesudah nilai lazy diteruskan ke anak-anak, segmen tersebut sudah bersih. Tidak ada lagi nilai lazy, sehingga delayedAdd perlu dijadikan 0.
Langkah kedua, lakukan update pada anak-anak segmen seperlunya.
Terakhir, perbaharui nilai segmen saat ini berdasarkan informasi dari anak-anaknya. Hal ini perlu dilakukan karena segmen tersebut sudah terbebas dari nilai lazy, yang mana telah diteruskan ke anak-anaknya.
Perhatikan bahwa anak-anaknya mungkin menyimpan nilai lazy. Ketika suatu segmen menyimpan nilai lazy, nilai asli jumlahan yang dikandung segmen itu adalah: sum + delayedAdd*banyaknya_elemen. Supaya rapi, saya mendefinisikan fungsi "GET" untuk mendapatkan nilai asli suatu segmen. Berhubung banyaknya elemen dalam segmen diperlukan, saya menjadikan batasan kiri dan kanan segmen sebagai parameter dalam "GET":
Sadari bahwa proses menempatkan nilai lazy pada base case sebenarnya memiliki konsep yang sama dengan menempatkan nilai lazy kepada anak-anak dalam fungsi "PROPAGATE". Supaya lebih rapi, kita bisa me-refactor-nya menjadi sebuah fungsi "LAZY_UPDATE":
Dan selesailah fungsi update. Lanjut ke fungsi query yang konsepnya mirip.
Mulai dengan membuat kasus ketika segmen sepenuhnya dicakupi rentang yang ditanyakan. Pada kasus ini, cukup kembalikan nilai sum + delayedAdd*banyaknya_elemen. Hal ini sama dengan fungsi "GET" yang telah kita buat, jadi cukup digunakan kembali:
Untuk kasus anaknya perlu diperiksa, kita akan mengulang ketiga proses seperti pada update. Pertama, lakukan propagate nilai lazy ke anak-anaknya:
Kedua, query anak-anaknya yang mengandung rentang yang ditanyakan:
Terakhir, perbaharui nilai segmen ini menggunakan informasi dari anak-anaknya. Kembali diulang bahwa ini perlu dilakukan karena segmen tersebut sudah terbebas dari nilai lazy, yang mana telah diteruskan ke anak-anaknya. Selesailah fungsi query, dan jangan lupa untuk return nilai di akhir.
Berhubung proses memperbaharui nilai orang tua dari anak-anaknya digunakan di update dan query, saya me-refactor-nya ke dalam fungsi "MERGE". Berikut implementasi lengkap untuk HORRIBLE:
Demikianlah implementasi lazy propagation pada soal yang klasik. Polanya sudah terlihat dari implementasi kedua fungsi di atas, yaitu:
- Apabila segmen ini dicakup sepenuhnya pada rentang yang diminta, lakukan LAZY_UPDATE (untuk update) atau GET (untuk query).
- Apabila segmennya tidak dicakup sepenuhnya pada rentang yang diminta, telusuri anak-anaknya.
- Sebelum melanjutkan operasi, lakukan dulu PROPAGATE yang akan mewariskan nilai lazy segmen ke anak-anaknya menggunakan LAZY_UPDATE.
- Teruskan operasi ke anak-anaknya.
- Baik untuk update maupun query, lakukan MERGE untuk mencari nilai asli (tanpa nilai lazy-lazy-an) dari segmen tersebut menggunakan GET dari anak-anaknya.
- LAZY_UPDATE
- GET
- PROPAGATE
- MERGE
Mari kita lihat studi kasus berikutnya untuk memperjelas pemahaman tentang implementasi keempat fungsi tersebut.
Studi Kasus 2: Circular RMQ (Codeforces)
Soal lengkap dapat dibaca di sini: https://codeforces.com/contest/52/problem/C
Intinya adalah, diberikan array bilangan a dan 2 macam operasi:- inc(l, r, v): tambahkan v pada a[l], a[l+1], a[l+2], ..., a[r].
- rmq(l, r): cari nilai terkecil di antara a[l], a[l+1], a[l+2], ..., a[r].
Urusan sirkularnya tidak menjadi masalah, sebab operasi yang "menembus" elemen terakhir dapat dipecah menjadi 2. Contohnya operasi pada elemen ke 8 sampai ke 3 pada array zero-based dengan 10 elemen cukup dilakukan pada a[8..9] dan a[0..3] secara terpisah.
Nilai yang wajib kita simpan jelas adalah nilai elemen terkecil dari suatu segmen. Lalu apa nilai lazy-nya? Secara intuitif kita dapat menggunakan konsep yang serupa dengan soal sebelumnya, yaitu "delayedAdd".
Apakah dengan "delayedAdd" kita bisa mendapatkan nilai terkecil dari suatu segmen dengan efisien tanpa melirik anak-anaknya? Jawabannya: ya, karena nilai terkecilnya pastilah nilai terkecil yang tersimpan ditambah "delayedAdd".
Nilai yang wajib kita simpan jelas adalah nilai elemen terkecil dari suatu segmen. Lalu apa nilai lazy-nya? Secara intuitif kita dapat menggunakan konsep yang serupa dengan soal sebelumnya, yaitu "delayedAdd".
Apakah dengan "delayedAdd" kita bisa mendapatkan nilai terkecil dari suatu segmen dengan efisien tanpa melirik anak-anaknya? Jawabannya: ya, karena nilai terkecilnya pastilah nilai terkecil yang tersimpan ditambah "delayedAdd".
Saya persilakan Anda untuk memahami implementasi berikut untuk lebih jelasnya. Fungsi update dan query nyaris sama persis dengan fungsi yang sama pada kode HORRIBLE. Yang berbeda signifikan hanya cara mengimplementasikan keempat fungsi abstraknya.
Studi Kasus 3: Ahoy Pirates (UVa)
Soal lengkap dapat dibaca di: UVa 11402.
Kali ini kita diberikan barisan berisi nilai 0 dan 1. Angka 0 menyatakan "Barbary" dan angka 1 menyatakan "Buccaneer".
Terdapat beberapa jenis operasi yang disebut "sihir" oleh soalnya:
- F a b: ubah elemen ke-a sampai elemen ke-b menjadi angka 1
- E a b: ubah elemen ke-a sampai elemen ke-b menjadi angka 0
- I a b: ubah elemen ke-a sampai elemen ke-b dari 0 menjadi 1, atau dari 1 menjadi 0 (dibalik)
- S a b: hitung banyaknya angka 1 dari elemen ke-a sampai elemen ke-b
Untuk melayani operasi I, kita bagi per kasusnya:
- Ketika segmen berada dalam pengaruh F, kini menjadi E
- Ketika segmen berada dalam pengaruh E, kini menjadi F
- Jika tidak dalam pengaruh sihir apa-apa, kita tandakan bahwa segmen ini berada dalam efek I.
- Jika ternyata segmen ini berada dalam efek I, kini menjadi tidak dalam pengaruh sihir apa-apa.
Setelah memahami bagaimana melayani operasi F, E, dan I, kita selesai mendefinisikan bagaimana fungsi LAZY_UPDATE bekerja.
Untuk operasi GET, jelas kita perlu menyimpan banyaknya elemen bernilai 1 pada suatu segmen. Mari kita sebut banyaknya elemen bernilai 1 dalam suatu segmen sebagai "nBuc". Saat teradpat nilai lazy, nilai nBuc sesungguhnya dapat dicari dengan cara berikut:
Untuk operasi GET, jelas kita perlu menyimpan banyaknya elemen bernilai 1 pada suatu segmen. Mari kita sebut banyaknya elemen bernilai 1 dalam suatu segmen sebagai "nBuc". Saat teradpat nilai lazy, nilai nBuc sesungguhnya dapat dicari dengan cara berikut:
- Jika sedang dalam pengaruh F, kembalikan banyaknya elemen yang dicakup segmen tersebut.
- Jika sedang dalam pengaruh E, kembalikan 0.
- Jika tidak sedang dalam pengaruh sihir apa-apa, kembalikan nBuc.
- Jika sedang dalam pengaruh I, kembalikan banyaknya elemen 0, yang sama saja dengan banyaknya elemen segmen tersebut dikurangi nBuc.
Setelah LAZY_UPDATE dan GET didefinisikan, PROPAGATE dan MERGE tinggal mengikuti saja. Lagi-lagi fungsi update dan query nyaris sama persis dengan fungsi yang sama pada kode HORRIBLE. Perbedaan signifikan hanya dalam cara mengimplementasikan keempat fungsi abstraknya. Berikut implementasi lengkapnya:
Latihan
Tiada kata "bisa" tanpa latihan. Silakan Anda coba terapkan lazy propagation pada soal-soal berikut:
SPOJ RPAR
SPOJ RPAR
Rasanya butuh waktu beberapa bulan sampai saya benar-benar paham cara kerja lazy propagation. Setelah mengulas 3 contoh, saya berharap penjelasan tentang lazy propagation menjadi jelas dan Anda menangkap gambaran kasarnya tanpa perlu menghabiskan berbulan-bulan seperti saya.
Tidak ada komentar :
Posting Komentar