Terdapat permintaan untuk menuliskan tentang range tree, jadi kali ini saya akan membahasnya dari awal.
Anda perlu diharapkan memiliki pengetahuan tentang apa itu segment tree terlebih dahulu.
Range tree yang saya tulis ini mungkin berbeda dengan range tree pada ilmu komputer pada umumnya. Saya akan membahas untuk spesifik range tree yang sering digunakan pada kompetisi pemrograman.
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). Tugas kita adalah menjawab sejumlah pertanyaan berupa:
"Pada daerah yang bermula di (x1, y1) sampai (x2, y2), ada berapa titik emasnya?"
Perhatikan gambar berikut.
Misalkan bulatan pada koordinat adalah titik yang mengandung sejumlah emas. Jawaban untuk banyaknya titik emas pada daerah yang bermula di (2, 2) sampai (8, 7) adalah 5.
Misalnya kita memiliki data koordinat sebagai berikut:
Kemudian urutkan setiap segmen berdasarkan nilai sumbu y. Hal ini mengakibatkan nilai sumbu-x pada setiap node berantakan, tetapi ini bukan masalah.
Selesailah pembuatan range tree. Konsepnya sangat sederhana.
Kompleksitas untuk membuat struktur yang mirip dengan segment tree adalah O(N log N).
Untuk setiap tingkat, total kompleksitas untuk mengurutkannya adalah O(N log N). Karena terdapat O(log N) ketinggian, maka kompleksitas pembangunan range tree adalah O(N log2 N).
Terdapat caranya supaya pembangunan range tree hanya O(N log N). Namun itu adalah cerita untuk lain hari.
Untuk memori, perhatikan bahwa tingkat pada range tree memiliki N elemen. Kembali lagi karena ketinggian dari tree adalah O(log N), didapatkan bahwa penggunaan memori range tree untuk N elemen adalah O(N log N).
Untuk setiap penelusuran pada suatu node, terdapat 3 kasus:
Perhatikan contoh berikut untuk mencari banyaknya titik dalam (2, 2) .. (8, 7). Warna merah menyatakan node yang memenuhi kasus ke-3, dan warna biru menyatakan data yang ditemukan dengan binary search. Ingat bahwa prosesnya adalah:
Setelah bagian memilah-milah segmen berdasarkan sumbu x, dijamin terdapat O(log N) segmen yang dipilih (seperti pada segment tree). Kemudian untuk setiap segmen dipilih, dilakukan binary search O(log N) pada titik-titik di dalamnya berdasarkan sumbu y. Sehingga kompleksitas untuk sekali menghitung banyaknya titik dalam daerah persegi panjang adalah O(log2 N).
"Pecah program besar menjadi beberapa komponen lebih kecil yang saling berinteraksi. Setiap komponen tidak perlu tahu implementasi komponen lainnya secara mendalam. Bila hal-hal tersebut dipenuhi, maka sakit kepala dapat dihindari".
Contoh untuk soal ini, ketika kita sedang berurusan dengan komponen x, kita tidak perlu peduli apa yang terjadi pada komponen y. Demikian juga kita tidak perlu peduli dengan nilai sumbu x ketika melakukan binary search. Hal ini membantu otak kita untuk fokus pada setiap komponen, ketimbang membuat program besar yang langsung mempertimbangkan seluruh komponen, yang mungkin mengakibatkan sakit kepala muncul.
Dalam rangka mendukung konsep "encapsulation", saya menganjurkan untuk mengimplementasikan node range tree menggunakan class atau struct pada C++, atau hal serupa pada bahasa pemrograman Anda. Saya akan menggunakan class pada C++ untuk tulisan ini.
Untuk keperluan implementasi, asumsikan kita memiliki struktur berikut:
Untuk node range tree, definisikan sebuah class yang menyimpan vector untuk menampung semua nilai y pada suatu node.
Kemudian definisikan beberapa variabel global:
Untuk tahap pertama, tampung dulu semua kemungkinan koordinat yang ada, kemudian lakukan kompresi pada sumbu-x.
Kompresi ini sebenarnya sesederhana mengurutkan seluruh sumbu x yang mungkin, lalu membuang nilai yang tidak unik. Hal ini akan mempermudah kita dalam membuat struktur range tree yang seimbang, hemat memori, dan bebas sakit kepala karena elemen yang tidak unik.
Setelah tahap kompresi, kita dapat memulai bagian membuat range tree. Definisikan fungsi untuk memasukkan data ke dalam range tree:
Selebihnya cukup masukkan semua data ke dalam range tree, dan urutkan tiap segmen.
Bagian menjawab pertanyaan, ikuti pembagian kasus yang telah dijelaskan pada bagian sebelumnya.
Perhatikan bahwa fungsi getCount didefinisikan dalam class RTreeNode. Dengan konsep encapsulation, kita membuat kode lebih mudah dibaca dan modular. Pada C++, Anda dapat menggunakan fungsi lower_bound dan upper_bound dari include algorithm:
Selesailah implementasi range tree untuk soal ini. Berikut kode lengkapnya:
Apabila terdapat beberapa titik dengan nilai sumbu-x yang sama, cukup ikuti algoritma yang sama. Artinya, setiap node pada range tree yang memiliki kedalaman sama mungkin memiliki banyaknya elemen berbeda. Meskipun terlihat "berat sebelah", hal ini tidak menjadi masalah, sebab operasi di dalam node tersebut adalah binary search O(log N) yang sangat cepat. Kompleksitas akhir selalu O(log2 N) untuk operasi pencarian.
Gambar berikut menunjukkan range tree dengan beberapa titik dengan komponen x dan y yang sama. Untuk kejelasan, perhatikan informasi tentang rentang x setiap node pada tulisan merah.
Petunjuk: soal ini bukan soal range tree "straight-forward". Namun Anda hanya butuh sebuah observasi untuk dapat mengubah soal ini menjadi "straight-forward". Sorot teks di bawah ini untuk spoiler:
Spoiler 1: lakukan binary search the answer. Coba tebak jawabannya, lalu cek berapa banyak elemen yang berada di dalam indeks yang diberikan, dan lebih kecil dari angka yang Anda tebak.
Spoiler 2: jika elemen ke-i bernilai vi, maka elemen tersebut dapat direpresentasikan sebagai titik di koordinat (i, vi).
UVa 12345 - Dynamic len(set(a[L:R]))
Spoiler 1: jika elemen ke-i dan ke-j memiliki nilai yang sama, dan tidak ada elemen di antaranya yang bernilai sama juga, maka tambahkan titik bernilai (i ,j) ke dalam range tree.
Spoiler 2: Banyaknya elemen unik pada suatu rentang a..b adalah seluruh elemen pada rentang tersebut, dikurangi titik-titik pada daerah (a,?)..(?,b).
Anda perlu diharapkan memiliki pengetahuan tentang apa itu segment tree terlebih dahulu.
Range tree yang saya tulis ini mungkin berbeda dengan range tree pada ilmu komputer pada umumnya. Saya akan membahas untuk spesifik range tree yang sering digunakan pada kompetisi pemrograman.
Tentang Range Tree
Range tree adalah struktur data yang dapat melayani operasi-operasi pada suatu daerah berbentuk persegi panjang secara efisien. Untuk contoh pembahasan ini, 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). Tugas kita adalah menjawab sejumlah pertanyaan berupa:
"Pada daerah yang bermula di (x1, y1) sampai (x2, y2), ada berapa titik emasnya?"
Perhatikan gambar berikut.
Misalkan bulatan pada koordinat adalah titik yang mengandung sejumlah emas. Jawaban untuk banyaknya titik emas pada daerah yang bermula di (2, 2) sampai (8, 7) adalah 5.
Konstruksi Range Tree
Range tree sangat mirip dengan segment tree. Perbedaannya adalah setiap node pada range tree tidak menyimpan nilai agregat, melainkan data yang tercakup dalam range-nya.Misalnya kita memiliki data koordinat sebagai berikut:
x: 1 2 4 5 6 7 8 9 y: 3 1 4 2 5 9 7 8Untuk membuat range tree, kita akan membagi-bagi data tersebut ke dalam struktur yang mirip dengan segment tree, berdasarkan nilai sumbu x.
Kemudian urutkan setiap segmen berdasarkan nilai sumbu y. Hal ini mengakibatkan nilai sumbu-x pada setiap node berantakan, tetapi ini bukan masalah.
Selesailah pembuatan range tree. Konsepnya sangat sederhana.
Kompleksitas untuk membuat struktur yang mirip dengan segment tree adalah O(N log N).
Untuk setiap tingkat, total kompleksitas untuk mengurutkannya adalah O(N log N). Karena terdapat O(log N) ketinggian, maka kompleksitas pembangunan range tree adalah O(N log2 N).
Terdapat caranya supaya pembangunan range tree hanya O(N log N). Namun itu adalah cerita untuk lain hari.
Untuk memori, perhatikan bahwa tingkat pada range tree memiliki N elemen. Kembali lagi karena ketinggian dari tree adalah O(log N), didapatkan bahwa penggunaan memori range tree untuk N elemen adalah O(N log N).
Menghitung Titik dalam Persegi Panjang
Operasi menghitung banyaknya titik dalam (x1, y1) .. (x2, y2) dilakukan dengan mudah. Mulai penelusuran dari root range tree.Untuk setiap penelusuran pada suatu node, terdapat 3 kasus:
- Node ini merepresentasikan segmen yang tidak bersentuhan dengan [x1, x2] pada sumbu x. Untuk kasus ini, hentikan penelusuran.
- Node ini merepresentasikan segmen yang bersentuhan [x1, x2] pada sumbu x, tetapi tidak berada di dalam [x1, x2]. Untuk kasus ini, telusuri kedua anak node ini.
- Kasus yang tersisa adalah node ini merepresentasikan segmen yang sepenuhnya berada di dalam [x1, x2] pada sumbu x. Untuk kasus ini, hitung banyaknya titik yang berada di dalam [y1, y2] pada sumbu y menggunakan binary search.
Perhatikan contoh berikut untuk mencari banyaknya titik dalam (2, 2) .. (8, 7). Warna merah menyatakan node yang memenuhi kasus ke-3, dan warna biru menyatakan data yang ditemukan dengan binary search. Ingat bahwa prosesnya adalah:
- Telusuri node-node (tree traversal) seperti pada segment tree.
- Untuk setiap node yang mencakup data bernilai sumbu-x di dalam [x1, x2], lakukan binary search.
Setelah bagian memilah-milah segmen berdasarkan sumbu x, dijamin terdapat O(log N) segmen yang dipilih (seperti pada segment tree). Kemudian untuk setiap segmen dipilih, dilakukan binary search O(log N) pada titik-titik di dalamnya berdasarkan sumbu y. Sehingga kompleksitas untuk sekali menghitung banyaknya titik dalam daerah persegi panjang adalah O(log2 N).
Implementasi Range Tree
Pada ilmu pemrograman, terdapat konsep bernama "encapsulation". Konsep ini kurang lebih menyatakan bahwa:"Pecah program besar menjadi beberapa komponen lebih kecil yang saling berinteraksi. Setiap komponen tidak perlu tahu implementasi komponen lainnya secara mendalam. Bila hal-hal tersebut dipenuhi, maka sakit kepala dapat dihindari".
Contoh untuk soal ini, ketika kita sedang berurusan dengan komponen x, kita tidak perlu peduli apa yang terjadi pada komponen y. Demikian juga kita tidak perlu peduli dengan nilai sumbu x ketika melakukan binary search. Hal ini membantu otak kita untuk fokus pada setiap komponen, ketimbang membuat program besar yang langsung mempertimbangkan seluruh komponen, yang mungkin mengakibatkan sakit kepala muncul.
Dalam rangka mendukung konsep "encapsulation", saya menganjurkan untuk mengimplementasikan node range tree menggunakan class atau struct pada C++, atau hal serupa pada bahasa pemrograman Anda. Saya akan menggunakan class pada C++ untuk tulisan ini.
Untuk keperluan implementasi, asumsikan kita memiliki struktur berikut:
Untuk node range tree, definisikan sebuah class yang menyimpan vector untuk menampung semua nilai y pada suatu node.
Kemudian definisikan beberapa variabel global:
Untuk tahap pertama, tampung dulu semua kemungkinan koordinat yang ada, kemudian lakukan kompresi pada sumbu-x.
Kompresi ini sebenarnya sesederhana mengurutkan seluruh sumbu x yang mungkin, lalu membuang nilai yang tidak unik. Hal ini akan mempermudah kita dalam membuat struktur range tree yang seimbang, hemat memori, dan bebas sakit kepala karena elemen yang tidak unik.
Setelah tahap kompresi, kita dapat memulai bagian membuat range tree. Definisikan fungsi untuk memasukkan data ke dalam range tree:
Selebihnya cukup masukkan semua data ke dalam range tree, dan urutkan tiap segmen.
Bagian menjawab pertanyaan, ikuti pembagian kasus yang telah dijelaskan pada bagian sebelumnya.
Perhatikan bahwa fungsi getCount didefinisikan dalam class RTreeNode. Dengan konsep encapsulation, kita membuat kode lebih mudah dibaca dan modular. Pada C++, Anda dapat menggunakan fungsi lower_bound dan upper_bound dari include algorithm:
- lower_bound(arr.begin(), arr.end(), x): mengembalikan iterator pada arr yang menunjuk ke elemen pertama yang >= x
- upper_bound(arr.begin(), arr.end(), x): mengembalikan iterator pada arr yang menunjuk ke elemen pertama yang > x
Selesailah implementasi range tree untuk soal ini. Berikut kode lengkapnya:
Catatan Implementasi
Pada penjelasan dan gambar-gambar yang saya berikan, tidak ada dua titik dengan nilai sumbu-x yang sama. Ini sekedar untuk mempermudah penjelasan.Apabila terdapat beberapa titik dengan nilai sumbu-x yang sama, cukup ikuti algoritma yang sama. Artinya, setiap node pada range tree yang memiliki kedalaman sama mungkin memiliki banyaknya elemen berbeda. Meskipun terlihat "berat sebelah", hal ini tidak menjadi masalah, sebab operasi di dalam node tersebut adalah binary search O(log N) yang sangat cepat. Kompleksitas akhir selalu O(log2 N) untuk operasi pencarian.
Gambar berikut menunjukkan range tree dengan beberapa titik dengan komponen x dan y yang sama. Untuk kejelasan, perhatikan informasi tentang rentang x setiap node pada tulisan merah.
Latihan
SPOJ MKTHNUMPetunjuk: soal ini bukan soal range tree "straight-forward". Namun Anda hanya butuh sebuah observasi untuk dapat mengubah soal ini menjadi "straight-forward". Sorot teks di bawah ini untuk spoiler:
Spoiler 1: lakukan binary search the answer. Coba tebak jawabannya, lalu cek berapa banyak elemen yang berada di dalam indeks yang diberikan, dan lebih kecil dari angka yang Anda tebak.
Spoiler 2: jika elemen ke-i bernilai vi, maka elemen tersebut dapat direpresentasikan sebagai titik di koordinat (i, vi).
UVa 12345 - Dynamic len(set(a[L:R]))
Spoiler 1: jika elemen ke-i dan ke-j memiliki nilai yang sama, dan tidak ada elemen di antaranya yang bernilai sama juga, maka tambahkan titik bernilai (i ,j) ke dalam range tree.
Spoiler 2: Banyaknya elemen unik pada suatu rentang a..b adalah seluruh elemen pada rentang tersebut, dikurangi titik-titik pada daerah (a,?)..(?,b).
Tidak ada komentar :
Posting Komentar