Struktur Data Binary Indexed Tree (BIT)

Dikenal juga sebagai struktur data Fenwick Tree

Saya sering menyebutkan struktur data ini pada tulisan-tulisan saya yang sebelumnya. Biasanya saya mencantumkan link ke halaman tutorial Fun Programming Club Ristek Fasilkom UI (organisasi semacam "klub programming"). Namun kini webnya sudah berubah, dan tulisan yang lama sudah menghilang. Untuk itu saya akan menuliskannya di blog ini.

Struktur data ini memiliki kegunaan yang mirip dengan segment tree. Hal yang dapat dikerjakan BIT, dapat dikerjakan segment tree, tetapi belum tentu sebaliknya. Mari kita mulai dengan persoalan motivasi.

---

Persoalan Motivasi

Diberikan sebuah array A yang berisi N bilangan. Array A terdefinisi untuk A[1..N] (one-based). Terdapat sejumlah perintah yang masing-masing dapat berbentuk:

1. update(x, v), artinya tambah nilai di indeks x sebanyak v.
2. query(x), artinya cari nilai A[1] + A[2] + ... + A[x].

Tentunya, kita dapat menyelesaikan persoalan ini dengan cara naif, update O(1) dan query O(N). Sayangnya cara ini terlalu lambat.

Segment tree dapat dengan mudah menyelesaikan masalah ini, dengan update O(log N) dan query O(log N). Namun mari kita coba bahas dengan BIT.

Radix Sort

Bahasan kali ini bukan sesuatu yang berat, yaitu sekedar radix sort.

Orang-orang yang telah menguasai algoritma pengurutan tingkat lanjut pasti tahu tentang jenis pengurutan ini. Algoritmanya sendiri memiliki konsep yang sederhana. Namun di balik konsep sederhana itu, implementasinya mungkin tidak semudah yang dibayangkan. Alasan saya menulis topik ini adalah memperkenalkan implementasinya, yang ternyata menggunakan stable counting sort.

Pengurutan ini cukup unik, untuk mengurutkan N angka yang memiliki paling banyak d digit, kompleksitasnya adalah O(Nd). Untuk nilai d yang kurang dari log N, algoritma ini lebih cepat dari pengurutan O(N log N).

Binary Search pada Sparse Table

Terdapat suatu teknik optimisasi yang dapat digunakan pada binary search. Biasanya teknik ini akan membuang faktor sebesar O(log N). Jadi kalau tadinya algoritma berjalan dalam O(log² N), sekarang menjadi O(log N) saja.

Teknik dapat digunakan pada binary search yang dilakukan pada Sparse Table.

---

Persoalan Motivasi

Misalnya dimiliki N batu pijakan di danau, yang strukturnya seperti lingkaran. Batu-batu dinomori dari 0 sampai dengan N-1. Berhubung bentuknya siklik, batu i bertetangga dengan batu (i-1) dan (i+1). Tentunya batu 0 bertetangga dengan batu N-1 dan 1. Diketahui pula bahwa apabila seseorang berdiri di batu ke-i, maka dia hanya dapat berpindah tempat ke batu (i+t[i]) mod N. Pertanyaannya adalah, apabila seseorang bediri di suatu posisi x, berapa banyak aktivitas berpindah tempat minimal yang perlu ia lakukan supaya ia memutari satu lingkaran?

Misalnya untuk ilustrasi berikut, banyaknya berpindah tempat yang perlu dilakukan adalah 6 kali. Supaya mudah, saya memodelkan setiap posisi (i+t[i]) mod N sebagai anak panah.

SPOJ QMAX3VN - BST Sebagai Segment Tree

Berikut adalah kelanjutan dari tulisan saya tentang penggunaan BST untuk menjawab dynamic range query. Soal yang dibahas adalah SPOJ QMAX3VN.

---

Ide solusi

Soal ini merupakan implementasi langsung dari konsep BST sebagai "segment tree" yang saya bahas sebelumnya. Pilihlah suatu jenis BBST yang Anda sukai, baik itu AVL Tree, Red Black Tree, Treap, atau Splay Tree.

Nilai agregat pada soal ini jelas adalah nilai terbesar yang ada pada suatu subtree. Anda juga perlu menyimpan banyaknya elemen yang ada pada suatu subtree, supaya dapat menentukan apakah suatu node/subtree berada dalam rentang query.

Tips untuk mengimplementasikannya:

1. Definisikan fungsi updateAggregate untuk melakukan update pada nilai agregat suatu node, menggunakan data dari anak kiri dan anak kanannya. Aktivitas updateAggregate akan digunakan di banyak tempat, sehingga mendefinisikannya sebagai fungsi akan mempermudah penulisan kode. Pastikan kompleksitasnya O(1).
2. Jika BST Anda menggunakan rotasi, pastikan pemanggilan updateAggregate sesuai urutannya, yaitu dari node anak-anak dulu, baru ke orang tuanya.
3. Definisikan fungsi getMax dan getCount untuk mendapatkan nilai terbesar dan banyaknya node pada suatu subtree, yang mampu menangani kasus ketika node yang diberikan adalah null. Pendefinisian fungsi ini sangat membantu dalam mengeliminasi if statement untuk null di banyak tempat. Pastikan juga kompleksitasnya O(1).

BST Sebagai Segment Tree

Tahukah Anda bahwa BST dapat digunakan untuk menjawab dynamic range query, seperti mencari nilai terkecil/terbesar dari suatu rentang array? Atau juga hal-hal lebih kompleks lainnya seperti mencari subarray dengan jumlahan terbesar. Tulisan ini akan menjelaskan konsep membuat BST yang mampu melayani query tersebut, lalu menjelaskan kenapa kita membutuhkannya.

Sebagai catatan, BST yang saya maksud di sini adalah Binary Search Tree yang balanced, alias BBST.

---

Konsep Dasar

Terdapat beberapa konsep tentang BST yang perlu dipahami terlebih dahulu. Simak penjelasannya satu per satu.

Rumus Dynamic Programming

Awal Perjumpaan

Malam hari saat pertama kali ikut OSN 2009, saya membaca buku TOKI News. Ada beberapa pembahasan soal di sana, dan sepertinya cocok untuk memanaskan diri sebelum kompetisi.

Kemudian yang saya lihat adalah rumus ajaib yang tiba-tiba muncul setelah kata-kata "Dynamic Programming" disebut:

Berhubung saya waktu itu tidak mengerti, saya lompat ke pembahasan soal lainnya. Buka-buka halaman di belakang, baca soalnya, lalu pembahasannya. Kemudian yang saya temui adalah ini:

Mengenal Expected Value (Nilai Harapan)

Dulu ketika zamannya saya ikut SRM top coder, kalau dapat soal dengan kalimat perintah "Find the expected value of ...", saya langsung merasa seram. Alasannya karena saya tidak tahu apa itu expected number. Belum lagi tiba-tiba contoh keluaran yang ada adalah angka pecahan yang misterius, contohnya:

1.12938104018102

Kemudian suatu ketika saya mendapatkan pencerahan, bahwa ternyata expected value adalah nilai harapan. Seketika saya langsung bisa mengerjakan soal-soal dasar tentang expected value.

Tulisan ini akan menjelaskan apa itu expected value, supaya kalian para pembaca tidak merasa seram seperti saya dulunya.

Struktur Data Sparse Table

Kali ini saya membahas tentang struktur data yang menurut saya jarang diajarkan secara formal. Selama ini saya mempelajarinya sebagai bagian dari suatu algoritma lebih besar, seperti pencarian LCA (Lowest Common Ancestor) atau RMQ (Range Minimum Query).

---

Permasalahan Motivasi

Terdapat N orang di sebuah ruangan. Terdapat sebuah bola panas, yang awalnya diberikan pada seseorang. Ketika orang ke-i menerima bola panas ini, ia akan mengoper bola panas itu ke orang ke-p[i]. Proses menerima bola dan mengopernya terjadi dalam satu periode yang disebut satu putaran.

Kemudian Anda diberikan banyak pertanyaan berbunyi:
Ditentukan suatu angka X dan Y. Bila awalnya orang yang menerima bola panas adalah orang ke-X, maka dalam Y putaran berikutnya, di mana bola panas itu berada?

Asumsikan X dan Y tidak lebih dari N.

Amortized Analysis

Jika Anda belajar library bernama "vector" di C++, maka mungkin Anda pernah mendengar bahwa kompleksitas push_back adalah amortized O(1). Apa yang dimaksud dengan amortized?

Penerjemahan langsung ke Bahasa Indonesia agak lucu, yaitu "dilunasi dengan angsuran". Untuk lebih memahaminya, lebih baik kita membahas contoh soalnya, yaitu push_back pada vector.

Permasalahan

Anda ingin membuat array, tetapi tidak mengetahui banyaknya elemen maksimal yang mungkin ditampung dalam suatu waktu. Salah satu cara yang dapat dilakukan adalah menggunakan "resize-able array".

Pertama mulai dengan sebuah array yang maksimal dapat menampung X elemen. Misalkan X kita beri nilai 10. Operasi menambahkan elemen di paling belakang awalnya array dapat dilakukan dengan cara kira-kira seperti ini:

Panduan Menulis Kaget

Apakah Anda orang yang tiba-tiba:

• Hendak mengarang untuk tugas sekolah/kuliah?
• Hendak menulis soal untuk kontes?
• Harus menulis skripsi karena deadline menulis tinggal beberapa hari?
• Ditunjuk untuk menulis materi/pembahasan?

Jika ya, maka Anda mungkin mendapat manfaat dari membaca panduan menulis kaget berikut. Saya sebut kaget karena tulisan ini bersifat tiba-tiba, seperti pasar kaget.

Ilmu menulis saya didapatkan dari senior-senior TOKI dan dosen yang sudah ahli dalam menulis soal atau dokumen resmi. Pengaruh paling besar yang saya dapatkan adalah dari Ashar. Berterimakasihlah pada Ashar.

Saya bukan ahli bahasa. Saya hanya orang yang entah kenapa sering menulis.