Sejauh ini saya sudah pernah membahas struktur data:
Ada juga struktur data yang menarik untuk digunakan:
Dan ada juga struktur data yang lebih jarang digunakan:
Masing-masing struktur data tersebut memiliki peran dan kegunaan masing-masing. Oleh karena itu, ketika sedang mengerjakan soal dynamic range query non-klasik, pertanyaan yang muncul adalah "dikerjakan pakai struktur data apa ya?"
Menurut pengalaman saya, tidak semua persoalan dapat diselesaikan cukup dengan satu jenis struktur data. Untuk soal-soal yang lebih sulit, Anda membutuhkan kombinasi dari struktur data yang ada, atau generalisasi struktur data tersebut (menjadi dua dimensi, atau mungkin tiga dimensi). Pernahkah terbayangkan untuk membuat segment tree di dalam range tree? Atau BBST di dalam range tree? Atau bahkan segment tree di dalam segment tree lagi? Kenyataannya, hal-hal itu bisa dilakukan!
Salah satu contoh persoalan yang menarik dalam kasus ini adalah soal Arnooks's Defensive Line (LA 5871, ICPC Regional Kuala Lumpur 2011). Inti soal ini sederhana: diberikan sejumlah operasi penambahan interval, dan sewaktu-waktu bisa ditanyakan berapa banyak interval yang sepenuhnya berada di dalam suatu interval yang diberikan, laksanakan secara efisien!
Salah satu solusi yang mungkin adalah memetakan interval (a, b) sebagai titik. Kemudian query yang bertanya banyaknya interval yang sepenuhnya berada di dalam (p, q) bisa dilakukan dengan mencari banyaknya titik (x, y) yang memenuhi p ≤ x dan y ≤ q. Operasi query itu juga mirip dengan mencari banyaknya titik di dalam sub-persegipanjang (p, 0) sampai (∞, q). Karena yang perlu dilakukan sangat mirip dengan pekerjaan yang dilayani oleh range tree, maka penggunaan range tree bisa menjadi salah satu solusinya.
Dalam implementasinya, range tree dibuat dengan segment tree yang isinya adalah vector. Karena query yang dibutuhkan adalah daerah sub-persegipanjang, maka diperlukan segment tree lagi pada vector tersebut. Jadi wujud sebenarnya adalah segment tree dalam segment tree (yo dawg!). Kompleksitas untuk sekali operasi (insersi atau query) adalah O(log2N).
Saya pernah coba mengimplementasikannya, dan setelah dikumpulkan ke SPOJ (KL11B), hasil yang saya dapatkan adalah TLE! Bahkan setelah saya comment bagian query-nya (jadi hanya insersi saja), juga sudah TLE. Sebenarnya tidak heran juga, karena segment tree memiliki nilai konstanta yang besar. Penempatan segment tree dua lapis itu jelas meningkatkan konstantanya secara kuadratik.
Berikutnya, saya mencoba struktur data yang konstantanya lebih ringan (meskipun kompleksitasnya agak lebih besar), yaitu segment array. Sekarang kompleksitasnya untuk setiap operasi adalah \(O(\sqrt{N} \log{\sqrt{N}})\) untuk setiap operasi. Ternyata masih juga TLE!
Berbagai strategi saya gunakan dan belum juga berhasil AC. Saya juga berdiskusi dengan Pak Denny (coach ICPC Fasilkom UI), dan Pak Denny sendiri sudah mengimplementasikan quad tree & interval tree tetapi masih belum AC juga. Setelah menyerah, akhirnya saya googling dan mendapatkan pencerahan yang luar biasa.
Terdapat beberapa forum, salah satunya dari Topcoder. Forum itu kebakaran (istilah dari Reinhart, untuk forum yang orang-orang yang berdiskusi di dalamnya memiliki rating merah/kuning). Ada juga forum dari codeforces dan mereka menjelaskan solusi yang digunakan. Ternyata solusi yang bisa AC adalah dengan BIT + treap!
Bila diperhatikan, solusi range tree sebenarnya adalah segment tree yang diisi dengan segment tree lagi. Bagaimana dengan BIT dan treap? BIT akan menggantikan kegunaan segment tree lapisan pertama, dan treap akan menggantikan segment tree bagian dalamnya (mengapa tidak BIT lagi? Bisa saja, tetapi implementasinya agak rumit karena harus melakukan grid compression). Meskipun tidak umum, hal ini bisa dilakukan. BIT dan treap terkenal sebagai struktur data yang memiliki konstanta ringan, sehingga tidak heran apabila O(log2N) yang mereka hasilkan sangat cepat.
Yang ingin saya sampaikan adalah struktur data dapat di-"mix & match" sesuai dengan kebutuhan, sehingga tidak terbatas bahwa BIT harus berisi angka, segment tree hanya untuk RMQ, dsb. Pada kenyataannya, kita bisa membuat range tree dengan BIT yang isinya adalah segment tree atau treap. Bahkan saya pun pernah membuat disjoint set yang isinya adalah priority queue!
Berikut ini contoh-contoh kode kombinasi maut yang pernah saya buat:
Demikian tulisan saya kali ini. Selamat meracik struktur data yang efisien :)
Ada juga struktur data yang menarik untuk digunakan:
- BBST (AVL tree atau Red-Black Tree)
- Segment array [1]
- Range tree [1] (sering diimplementasikan sebagai segment tree dengan nilai agregat berupa vector)
Dan ada juga struktur data yang lebih jarang digunakan:
- Kd Tree
- Quad Tree
- Interval Tree
Masing-masing struktur data tersebut memiliki peran dan kegunaan masing-masing. Oleh karena itu, ketika sedang mengerjakan soal dynamic range query non-klasik, pertanyaan yang muncul adalah "dikerjakan pakai struktur data apa ya?"
Menurut pengalaman saya, tidak semua persoalan dapat diselesaikan cukup dengan satu jenis struktur data. Untuk soal-soal yang lebih sulit, Anda membutuhkan kombinasi dari struktur data yang ada, atau generalisasi struktur data tersebut (menjadi dua dimensi, atau mungkin tiga dimensi). Pernahkah terbayangkan untuk membuat segment tree di dalam range tree? Atau BBST di dalam range tree? Atau bahkan segment tree di dalam segment tree lagi? Kenyataannya, hal-hal itu bisa dilakukan!
Salah satu contoh persoalan yang menarik dalam kasus ini adalah soal Arnooks's Defensive Line (LA 5871, ICPC Regional Kuala Lumpur 2011). Inti soal ini sederhana: diberikan sejumlah operasi penambahan interval, dan sewaktu-waktu bisa ditanyakan berapa banyak interval yang sepenuhnya berada di dalam suatu interval yang diberikan, laksanakan secara efisien!
Salah satu solusi yang mungkin adalah memetakan interval (a, b) sebagai titik. Kemudian query yang bertanya banyaknya interval yang sepenuhnya berada di dalam (p, q) bisa dilakukan dengan mencari banyaknya titik (x, y) yang memenuhi p ≤ x dan y ≤ q. Operasi query itu juga mirip dengan mencari banyaknya titik di dalam sub-persegipanjang (p, 0) sampai (∞, q). Karena yang perlu dilakukan sangat mirip dengan pekerjaan yang dilayani oleh range tree, maka penggunaan range tree bisa menjadi salah satu solusinya.
Dalam implementasinya, range tree dibuat dengan segment tree yang isinya adalah vector. Karena query yang dibutuhkan adalah daerah sub-persegipanjang, maka diperlukan segment tree lagi pada vector tersebut. Jadi wujud sebenarnya adalah segment tree dalam segment tree (yo dawg!). Kompleksitas untuk sekali operasi (insersi atau query) adalah O(log2N).
Saya pernah coba mengimplementasikannya, dan setelah dikumpulkan ke SPOJ (KL11B), hasil yang saya dapatkan adalah TLE! Bahkan setelah saya comment bagian query-nya (jadi hanya insersi saja), juga sudah TLE. Sebenarnya tidak heran juga, karena segment tree memiliki nilai konstanta yang besar. Penempatan segment tree dua lapis itu jelas meningkatkan konstantanya secara kuadratik.
Berikutnya, saya mencoba struktur data yang konstantanya lebih ringan (meskipun kompleksitasnya agak lebih besar), yaitu segment array. Sekarang kompleksitasnya untuk setiap operasi adalah \(O(\sqrt{N} \log{\sqrt{N}})\) untuk setiap operasi. Ternyata masih juga TLE!
Berbagai strategi saya gunakan dan belum juga berhasil AC. Saya juga berdiskusi dengan Pak Denny (coach ICPC Fasilkom UI), dan Pak Denny sendiri sudah mengimplementasikan quad tree & interval tree tetapi masih belum AC juga. Setelah menyerah, akhirnya saya googling dan mendapatkan pencerahan yang luar biasa.
Terdapat beberapa forum, salah satunya dari Topcoder. Forum itu kebakaran (istilah dari Reinhart, untuk forum yang orang-orang yang berdiskusi di dalamnya memiliki rating merah/kuning). Ada juga forum dari codeforces dan mereka menjelaskan solusi yang digunakan. Ternyata solusi yang bisa AC adalah dengan BIT + treap!
Bila diperhatikan, solusi range tree sebenarnya adalah segment tree yang diisi dengan segment tree lagi. Bagaimana dengan BIT dan treap? BIT akan menggantikan kegunaan segment tree lapisan pertama, dan treap akan menggantikan segment tree bagian dalamnya (mengapa tidak BIT lagi? Bisa saja, tetapi implementasinya agak rumit karena harus melakukan grid compression). Meskipun tidak umum, hal ini bisa dilakukan. BIT dan treap terkenal sebagai struktur data yang memiliki konstanta ringan, sehingga tidak heran apabila O(log2N) yang mereka hasilkan sangat cepat.
Yang ingin saya sampaikan adalah struktur data dapat di-"mix & match" sesuai dengan kebutuhan, sehingga tidak terbatas bahwa BIT harus berisi angka, segment tree hanya untuk RMQ, dsb. Pada kenyataannya, kita bisa membuat range tree dengan BIT yang isinya adalah segment tree atau treap. Bahkan saya pun pernah membuat disjoint set yang isinya adalah priority queue!
Berikut ini contoh-contoh kode kombinasi maut yang pernah saya buat:
- BIT + BIT, untuk soal SPOJ LIS2. Meskipun O(log2N) per operasi dan konstantanya ringan, solusi ini TLE :(. Kode sumber: [link]
- BIT + treap, untuk soal UVa 12003 - Array Transformer. Kode sumber: [link]
- Disjoint set + treap, untuk soal LA 5031 - Graph and Queries. Kode sumber: [link]
- Segment tree + AVL, untuk soal UVa 12345 - Dyanmic len(set(a[L:R])). Kode sumber: [link]
- Segment tree + segment tree, entah untuk soal apa (saya lupa). Soal UVa 12074 - The Ultimate Bamboo Eater dapat diselesaikan dengan struktur data serupa. Kode sumber: [link]
Demikian tulisan saya kali ini. Selamat meracik struktur data yang efisien :)
Tidak ada komentar :
Posting Komentar