Belakangan ini saya jadi sering menulis tentang segment tree. Berhubung masih terpikirkan, saya akan terus membagikan ilmu-ilmu aneh tentang segment tree.
Yang kali ini adalah lazy segment tree, yang berbeda dengan lazy propagation. Saya pernah menghadapi soal semacam ini, seingat saya di codeforces. Namun sayangnya tidak bisa saya temukan lagi padahal sudah mengorek-ngorek submission lama.
Inti soalnya adalah:
Seandainya soal ini boleh dikerjakan secara offline, solusinya sesederhana membaca seluruh query terlebih dahulu lalu grid compression. Meskipun terdapat 2 milyar elemen, sebenarnya hanya paling banyak 2N elemen yang mungkin disebut dalam operasi-operasinya.
Yang kali ini adalah lazy segment tree, yang berbeda dengan lazy propagation. Saya pernah menghadapi soal semacam ini, seingat saya di codeforces. Namun sayangnya tidak bisa saya temukan lagi padahal sudah mengorek-ngorek submission lama.
Inti soalnya adalah:
- Terdapat sebuah array dengan M elemen, yang mana M bisa sebesar 2 milyar.
- Pada awalnya setiap elemen bernilai 0.
- Terdapat N operasi berupa:
- U x y: artinya ubah elemen array di posisi ke-x menjadi y.
- Q x y: artinya cari elemen terbesar yang berada di antara elemen ke-x dan ke-y.
- Anda diwajibkan untuk mengerjakan operasi secara online (operasi berikutnya tidak dapat dibaca sebelum operasi saat ini dikerjakan)
Seandainya soal ini boleh dikerjakan secara offline, solusinya sesederhana membaca seluruh query terlebih dahulu lalu grid compression. Meskipun terdapat 2 milyar elemen, sebenarnya hanya paling banyak 2N elemen yang mungkin disebut dalam operasi-operasinya.
Solusi Binary Search Tree
Solusi langsung terpikirkan adalah menggunakan BST.
Cukup simpan elemen BST berupa pasangan data <indeks, nilai>. BST ini terurut berdasarkan indeks elemen. Setiap node perlu menyimpan nilai agregat berupa nilai terbesar antar elemen-elemen subtreenya. Kini seluruh operasi dapat dilakukan dalam O(log N).
Apabila Anda belum tahu apa itu BST, cek tulisan saya sebelumnya tentang treap.
Solusi Lazy Segment Tree
Solusi alternatifnya adalah dengan segment tree yang node-nya bersifat "lazy". Setiap node hanya dibuat apabila dia akan diakses. Nilai agregat dari segment tree ini adalah nilai terbesar yang diwakilkan oleh suatu segmen.
Pada awalnya, kita hanya memiliki sebuah node yang mencakup elemen 1 sampai dengan M. Kita tidak perlu membuat anak kiri dan kanannya untuk saat ini.
Kemudian untuk operasi "U x y", lakukan perubahan pada elemen ke-x seperti segment tree pada umumnya. Berhubung bisa saja terdapat node yang belum dibuat, inilah waktunya untuk membuat node tersebut. Setiap kali kita mengunjungi sebuah node yang belum memiliki anak kiri dan kanan, buat kedua anak tersebut, lalu lanjutkan operasi ke salah satu anak yang bersangkutan.
Node yang dibuat ini dipastikan memiliki nilai agregat 0. Pada akhirnya, terbentuk jalur "root to leaf" yang terlihat seperti "pengeboran". Dijamin terdapat paling banyak O(log M) node yang dibuat untuk setiap aktivitas pengeboran.
Untuk operasi "Q x y", lakukan hal yang serupa. Cukup lakukan operasi pencarian nilai terbesar seperti biasa sambil membuat node-node yang belum ada. Perhatikan bahwa bisa saja pembuatan node tidak sedalam sampai segmen yang mewakili 1 elemen; kita berhenti saat segmen yang saat ini dievaluasi berada di dalam cakupan [x, y].
Node biru menunjukkan segmen yang diperlukan untuk menjawab "Q x y"
Lagi-lagi dijamin terdapat paling banyak O(log M) node yang dibuat. Jadi kebutuhan memori untuk melakukan seluruh operasi adalah O(N log M).
Dari segi kompleksitas waktu, jelas bahwa setiap operasi juga berlangsung dalam O(log M). Kompleksitas waktu solusi ini adalah O(N log M).
Untuk implementasinya, saya senang membuat penampungan node-node ketimbang menggunakan pointer. Penampungan node ini dapat dibuat dengan vektor, dan setiap node kini dapat direferensikan menggunakan indeksnya di vektor tersebut. Berikut contoh implementasinya (tanpa enkripsi operasi):
Penutup
Pengetahuan ini mungkin tidak seberapa penting, tetapi lumayan untuk menambah ide bahwa kemalasan kadang-kadang dapat menyelesaikan masalah. Lagipula, kode yang ditulis lebih pendek dan sederhana dibandingkan menulis BST.
Semoga bermanfaat!
Semoga bermanfaat!
Tidak ada komentar :
Posting Komentar