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.