Tulisan ini adalah kelanjutan dari bagian pertama tentang pengenalan range tree.
Kini kita mampu menghitung banyaknya elemen di suatu daerah persegi panjang. Operasi lainnya yang sering dibutuhkan adalah pencarian nilai terbesar, terkecil, atau bahkan jumlahan elemennya. Kita akan menggunakan contoh soal berikut:
Pada suatu lahan, terdapat N titik yang mengandung sejumlah emas. Lahan ini dapat dianggap suatu bidang 2 dimensi. Titik ke-i memiliki koordinat (xi, yi), dan memiliki kandungan emas sebanyak vi kg. Tugas kita adalah menjawab sejumlah pertanyaan berupa:
"Pada daerah yang bermula di (x1, y1) sampai (x2, y2), berapa kandungan emas terbanyak yang ada pada suatu titik di daerah tersebut?"
Untuk mendapatkan nilai terbesar di suatu daerah persegi panjang, lakukan query range tree seperti cara sebelumnya. Nilai terbesar sebenarnya sesederhana nilai terbesar dari tiap-tiap nilai terbesar di setiap daerah yang kita cari. Dengan struktur yang telah kita pelajari, pencarian nilai terbesar di suatu node range tree perlu dilakukan melalui linear search, sehingga kompleksitasnya O(N) dan kurang efisien.
Sebetulnya pencarian nilai terbesar di suatu node range tree ini mengingatkan kita pada masalah klasik, yaitu mencari nilai terbesar dari subbarisan di array alias RMQ (Range Maximum Query).
Berikut ilustrasinya. Segment tree internal pada setiap node range tree yang diperlukan ditunjukkan dengan tree berwarna coklat.
Data yang perlu disimpan berupa y dan nilai dari setiap titik. Setelah seluruh titik dimasukkan ke dalam range tree, barulah setiap node range tree membangun segment tree internalnya.
Segment tree internal ini perlu dikompres secara parsial. Artinya, kita akan membangun pemetaan antara nilai y yang sesungguhnya dengan bilangan 0, 1, 2, ... dst, tetapi tidak dilakukan proses unique. Hal ini bertujuan untuk memungkinkan penyimpanan data dengan y yang sama tetapi kandungan emasnya berbeda. Kita tidak boleh semata-mata menggunakan nilai terbesar saja untuk beberapa titik dengan y yang sama, sebab ketika ada operasi perubahan nilai, implementasinya menjadi rumit.
Berikut implementasinya.
Terdapat maksimal O(log N) node range tree, dan masing-masing melakukan query pada segment tree internal. Strategi ini memberikan solusi berkompleksitas total O(log2N) per pencarian nilai terbesar di daerah persegi panjang.
Untuk dimensi d, kompleksitas sekali query adalah O(logdN). Untuk dimensi yang lebih dari 2, sebenarnya O(logdN) sudah mulai lambat. Apabila Anda menemukan soal yang memerlukan pembuatan range tree dengan dimensi lebih dari 2, coba perhatikan apakah ada dimensi yang bisa dihilangkan (misalnya melalui offline processing + line sweep).
Codeforces - Shooting Gallery
Spoiler 1: Lakukan offline processing + line sweep.
Spoiler 2: Anggap setiap kotak adalah range query untuk mencari tembakan terawal yang terjadi saat itu.
Kini kita mampu menghitung banyaknya elemen di suatu daerah persegi panjang. Operasi lainnya yang sering dibutuhkan adalah pencarian nilai terbesar, terkecil, atau bahkan jumlahan elemennya. Kita akan menggunakan contoh soal berikut:
Pada suatu lahan, terdapat N titik yang mengandung sejumlah emas. Lahan ini dapat dianggap suatu bidang 2 dimensi. Titik ke-i memiliki koordinat (xi, yi), dan memiliki kandungan emas sebanyak vi kg. Tugas kita adalah menjawab sejumlah pertanyaan berupa:
"Pada daerah yang bermula di (x1, y1) sampai (x2, y2), berapa kandungan emas terbanyak yang ada pada suatu titik di daerah tersebut?"
Ide Penyelesaian
Dengan ide pada tulisan sebelumnya, kita dapat membagi-bagi daerah berdasarkan sumbu x. Kemudian untuk setiap suatu rentang x, kita bagi berdasarkan sumbu y.Untuk mendapatkan nilai terbesar di suatu daerah persegi panjang, lakukan query range tree seperti cara sebelumnya. Nilai terbesar sebenarnya sesederhana nilai terbesar dari tiap-tiap nilai terbesar di setiap daerah yang kita cari. Dengan struktur yang telah kita pelajari, pencarian nilai terbesar di suatu node range tree perlu dilakukan melalui linear search, sehingga kompleksitasnya O(N) dan kurang efisien.
Sebetulnya pencarian nilai terbesar di suatu node range tree ini mengingatkan kita pada masalah klasik, yaitu mencari nilai terbesar dari subbarisan di array alias RMQ (Range Maximum Query).
Segment Tree Internal
Dengan ide bahwa pencarian nilai terbesar dalam node range tree sebenarnya merupakan RMQ, kita dapat membuat segment tree di dalam node range tree itu. Pada akhirnya, mencari nilai terbesar dari subbarisan di dalam node range tree dapat dilakukan dengan query segment tree, yang kompleksitasnya O(log N).Berikut ilustrasinya. Segment tree internal pada setiap node range tree yang diperlukan ditunjukkan dengan tree berwarna coklat.
Data yang perlu disimpan berupa y dan nilai dari setiap titik. Setelah seluruh titik dimasukkan ke dalam range tree, barulah setiap node range tree membangun segment tree internalnya.
Berikut implementasinya.
Terdapat maksimal O(log N) node range tree, dan masing-masing melakukan query pada segment tree internal. Strategi ini memberikan solusi berkompleksitas total O(log2N) per pencarian nilai terbesar di daerah persegi panjang.
Operasi Update
Segment tree internal ini juga dapat dimanfaatkan untuk mendukung operasi update. Pada contoh soal ini, anggap saja update ini berupa perubahan kandungan pada titik suatu emas.
Operasi ini dilakukan dengan memperbaharui nilai segment tree internal di setiap node range tree yang mengandung titik tersebut. Hanya terdapat O(log N) node range tree yang perlu diperbaharui. Untuk setiap node, update segment tree internalnya memiliki kompleksitas O(log N). Jadi sekali update range tree kompleksitasnya O(log2N).
Berikut ilustrasinya untuk proses update titik (4, 2) menjadi bernilai 5. Saya menunjukkan salah satu update pada segment tree internalnya.
Sebenarnya, ada keterbatasan dari operasi update ini. Kita tidak dapat menambah atau membuang titik. Apabila soal yang dihadapi memungkinkan dilakukan operasi offline (semua query dibaca dulu, baru dilakukan secara berurutan), maka trik yang dapat Anda gunakan adalah menganggap seluruh titik telah dimasukkan ke dalam range tree, dan memiliki nilai negatif tak berhingga. Barulah ketika titik tersebut ditambahkan secara sungguhan ke range tree, nilainya diganti menjadi nilai sesungguhnya. Cara ini menjamin titik yang belum ditambahkan secara sungguhan tidak mungkin menjadi jawaban untuk pencarian nilai terbesar.
Untuk sepenuhnya mendukung penambahan atau penghapusan data, Anda perlu mengganti segment tree internal ini dengan struktur data yang mampu secara efisien menangani penambahan/pengurangan. Struktur data itu misalnya Balanced Binary Search Tree (BBST), yang salah satu implementasinya dengan treap.
Operasi ini dilakukan dengan memperbaharui nilai segment tree internal di setiap node range tree yang mengandung titik tersebut. Hanya terdapat O(log N) node range tree yang perlu diperbaharui. Untuk setiap node, update segment tree internalnya memiliki kompleksitas O(log N). Jadi sekali update range tree kompleksitasnya O(log2N).
Berikut ilustrasinya untuk proses update titik (4, 2) menjadi bernilai 5. Saya menunjukkan salah satu update pada segment tree internalnya.
Sebenarnya, ada keterbatasan dari operasi update ini. Kita tidak dapat menambah atau membuang titik. Apabila soal yang dihadapi memungkinkan dilakukan operasi offline (semua query dibaca dulu, baru dilakukan secara berurutan), maka trik yang dapat Anda gunakan adalah menganggap seluruh titik telah dimasukkan ke dalam range tree, dan memiliki nilai negatif tak berhingga. Barulah ketika titik tersebut ditambahkan secara sungguhan ke range tree, nilainya diganti menjadi nilai sesungguhnya. Cara ini menjamin titik yang belum ditambahkan secara sungguhan tidak mungkin menjadi jawaban untuk pencarian nilai terbesar.
Untuk sepenuhnya mendukung penambahan atau penghapusan data, Anda perlu mengganti segment tree internal ini dengan struktur data yang mampu secara efisien menangani penambahan/pengurangan. Struktur data itu misalnya Balanced Binary Search Tree (BBST), yang salah satu implementasinya dengan treap.
Generalisasi ke Dimensi Tinggi
Kalau diperhatikan, sebenarnya range tree adalah segment tree yang mengandung segment tree. Strategi untuk membuat segment tree internal ini dapat digeneralisasi ke dimensi tiga atau lebih. Untuk dimensi 3, cukup buat node range tree terluar menampung sebuah range tree berdimensi 2, yang mana node range treenya menampung segment tree juga.
Latihan
Sorot teks di bawah soal untuk spoiler.Codeforces - Shooting Gallery
Spoiler 1: Lakukan offline processing + line sweep.
Spoiler 2: Anggap setiap kotak adalah range query untuk mencari tembakan terawal yang terjadi saat itu.
Penutup
Range tree bisa dikatakan pula adalah segment tree di dalam segment tree. Hal yang mengejutkan adalah, kita tidak selalu harus berpaku pada penggunaan segment tree. Bergantung pada kebutuhan soal, kita dapat mengimplementasikan range tree dengan segment tree di dalam BIT. Bukan hanya BIT, tetapi juga struktur data lain yang dapat Anda bayangkan selama itu membantu pemrosesan data secara efisien. Saya pernah membahas ini pada tulisan tentang komposisi struktur data. Sejauh ini saya pernah mengimplementasikan range tree dengan:
- Set di dalam segment tree (ICPC Regional Jakarta 2012 - Alien Abduction)
- BST di dalam BIT (ICPC Regional Kuala Lumpur 2011 - Arnooks's Defense Line)
- BIT di dalam BIT (SPOJ - LIS2)
Semoga bermanfaat!
Tidak ada komentar :
Posting Komentar