Struktur Data Range Tree

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.

---

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.

Pelatih Basket Gendut

(sesekali menulis yang tidak berkaitan dengan pemrograman)

Jika Anda pernah menonton film Slam Dunk, maka Anda mengenal Pak Anzai.

Pak Anzai dari cerita Slam Dunk
(dari http://annelialady.blogspot.com)

Pak Anzai, adalah pelatih bola basket pada film tersebut. Dulunya adalah seorang pemain, lalu sekarang sudah tua, gendut, dan pensiun. Saya mulai merasa diri saya seperti itu.

Sekarang saya sudah pensiun untuk competitive programming. Meskipun demikian, saya akan tetap menuliskan pengetahuan yang saya miliki, baik pada blog ini atau media lainnya.

Range Update BIT

... atau disebut juga magic BIT

Pada akhir semester ganjil tahun 2014, Pak Denny mengadakan inisiatif untuk latihan ICPC yang kita sebut sebagai latihan FURIOUS. Alasannya karena klub programming di UI disebutnya Fun Programming Club (FPC), dan kali ini kami ingin serius, sehingga namanya menjadi FURIOUS Programming Club (FPC). "IT IS NOT FUN ANYMORE" kata Aji.

Pada salah satu sesi latihan ini, kami mengerjakan soal Alien Abduction Again (LA 6443). Pada saat ICPC Jakarta 2013, tim saya (Vidina 2.0) berhasil menyelesaikan soal ini dengan segment tree yang konstantanya dioptimisasi habis-habisan. Menurut pembuat soal (Felix Halim), solusi yang diharapkan adalah menggunakan Binary Indexed Tree (BIT). Meskipun sama-sama O(log N) untuk setiap operasi, penggunaan BIT jauh lebih cepat dari segment tree dalam hal konstanta.

Dalam sesi latihan ini, kami berusaha mengerjakannya dengan BIT. Waktu itu ada saya, Ashar, Aji, dan Soko, yang berpikir habis-habisan dalam mencari tahu bagaimana solusinya dengan BIT. Yang kami tahu adalah dapat digunakan 2 BIT untuk suatu range query/update sum. Akhirnya kami berhasil memahami cara kerjanya, melakukan generalisasi untuk kasus umum, dan AC untuk soal tersebut. Aji menyebutnya dengan nama "magic BIT". Sejak saat itu saya pun ikut menyebutnya magic BIT.

---

Permasalahan Range Update

Terdapat sebuah array A berukuran N, yang terdefinisi dari indeks 1 sampai dengan N. Terdapat sejumlah operasi yang masing-masing bisa berupa salah satu dari:

1. add(a, b, v), artinya tambahkan seluruh elemen A dengan indeks antara a sampai b dengan v. Dengan kata lain, A[a..b] += v.
2. sum(x), artinya cari nilai A[1]+A[2]+A[3]+...+A[x].

Soal ini jelas dapat diselesaikan dengan segment tree dengan lazy propagation. Seperti biasa, mari kita coba selesaikan dengan BIT.

Grid Compression

Seperti judulnya, kali ini saya akan bercerita tentang grid compression. Sebelumnya ada suatu kisah.

Suatu ketika saat Pelatnas 2 TOKI 2011, terdapat soal yang menyeramkan. Saya tidak berhasil menemukan soal tersebut, tapi intinya seperti ini:

1. Terdapat ruang 2 dimensi
2. Akan dibangun sebuah gambar, dapat didekomposisi menjadi N persegi panjang
3. Persegi panjang ke-i terletak di koordinat (xi1, yi1) sampai dengan (xi2, yi2)
4. Beberapa persegi panjang boleh saja saling tumpang tindih
5. Wujud gabungan dari seluruh persegi panjang ini adalah gambar yang dimaksud
6. Cari keliling dan luas dari gambar ini!

Batasan:

• N ≤ 50
• 0 ≤ nilai seluruh koordinat ≤ 10⁹

Saya berpikir seharian, dan tidak menemukan bagaimana cara menyelesaikannya. Kemudian kami diberikan contoh solusi soal tersebut dalam bentuk kode. Saya menghabiskan semalaman untuk memahami kode tersebut, dan akhirnya mengerti penyelesaian solusinya.