Penggunaan Fenwick Tree / BIT

Pada post ini, saya mau mencoba membahas tentang penggunaan salah satu struktur data yang banyak dipakai di CP karena "kekuatannya" yang cukup hebat. Saya tidak membahas secara detail tentang BIT itu sendiri atau kenapa dia bisa bekerja (saya rasa tutorial Topcoder sudah cukup menjelaskan). Jadi, yang akan saya tulis cuma strategi penggunaan yang selama ini sudah pernah saya pakai :p Saya juga menyertakan contoh source code pada pembahasan soal yang saya taruh, jangan langsung dibuka, tapi buka hanya jika sudah "kepepet".

Oiya, tapi untuk tidak bingung pada beberapa bagian, saya beri sedikit fungsi BIT yang penting. BIT bisa dipakai pada fungsi yang memiliki inverse (semoga bener..), misalnya + (dibalik jadi -), xor (di-xor lagi). Karena itu, BIT tidak dapat digunakan untuk RMQ (Range Minimum / Maximum Query ), tapi ada sih di Codeforces yang menulis bisa (cek komentarnya), selain itu, bisa juga dilakukan dengan mudah jika rangenya pasti berbetuk [1,K], dengan ketentuan khusus yang akan dibahas.

1. Point Update - Point/Range Query
   
   Pada problem seperti ini, biasanya diberi beberapa query yang isinya seperti ini :
   
   
   • Update nilai index ke-a sebanyak / menjadi v
   • Tentukan nilai _sesuatu_  dari index ke-a sampai ke-b, di mana a <= b
   
   Untuk soal seperti ini, saya bagi dulu kasusnya agar lebih mudah :
   
   A. BIT pada 1D
   
   Ini merupakan persoalan paling dasar pada BIT. Untuk lebih mudah , lebih baik bahas salah satu soalnya, yaitu UVa - Ping Pong. Bahasa mudah dari soal ini : "Diberikan array yang panjangnya N, tentukan ada berapa triplet index i, j, k (i < j < k), sehingga array[ i ] > array[ j ] > array[ k ] atau array[ i ] < array[ j ] < array[ k ] ?"
   
   Tentunya mudah untuk membuat solusi O(N^3). Tapi pasti TLE :p
   Kemudian, solusi O(N^2) juga bisa didapat jika kita menghitung untuk tiap nilai j.Untuk tiap j yang mungkin, kita cek beberapa nilai :
   
   
   • Ada berapa nilai i, i < j, sehingga array[ i ] < array[ j ]. Misal ini val1
   • Ada berapa nilai i, i < j, sehingga array[ i ] > array[ j ]. Misal ini val2
   • Ada berapa nilai k, k > j, sehingga array[ k ] < array[ j ]. Misal ini val3
   • Ada berapa nilai k, k > j, sehingga array[ k ]  > array[ j ]. Misal ini val4
   
   
   Maka, nilai yang didapat dari indeks j tentunya sama dengan val1 * val4 + val2*val3. Tapi ini juga kemungkinan besar TLE.
   Menggunakan observasi yang sama dengan pendekatan sebelumnya, bisa didapat jika kita menghitung untuk tiap j dari kiri ke kana, val1 sampai val4 sebenarnya bisa dihitung dengan 2 buah BIT, yang masing-masing dipakai untuk menghitung val1,val2 dan untuk menghitung val3,val4.
   
   Kenapa?
   
   Perhatikan bahwa pada saat kita menghitung pada indeks j, sama saja dengan mengurangi kemunculan nilai array[ j ] untuk penghitungan val3 dan val4. Kemudian, setelah kita menghitung pada indeks j, sama saja dengan kita menambah kemunculan nilai array[ j ] untuk penghitungan val1 dan val2
   Oleh karena itu, kompleksitas bisa kita kurangi menjadi O(N log MAXX), di mana MAXX di sini bernilai 100000. Contoh Source Code
   
   Soal yang bisa dipakai latihan :
   
   
   • SPOJ - How to Handle the Fans
   • UVa - Ping Pong
   • UVa - Jupiter Attacks!
   • TLC - Lebih Dari
   • PEG - IOI '07 Pairs (tipe 2)
   
   B. Inversion Count
   
   Inti dari permasalahan ini adalah : "Diberikan array, tentukan ada berapa pasang i,j (i < j), sehingga array[ i ] > array[ j ] "
   Ini sebenarnya adalah persoalan klasik yang juga bisa diselesaikan dengan merge sort, tapi kali ini mari kita coba selesaikan menggunakan BIT. Contoh soalnya SPOJ - Insertion Sort
   Solusinya mirip seperti pembahasan pada Ping Pong, tapi lebih simple. Misal indeks-nya zero-based, jika kita menghitung untuk tiap j dari kecil ke besar, yang terjadi adalah :
   
   
   • Nilai pada indeks j sama dengan j - Query(array[ j ])
   • Selesai menghitung pada indeks j, lakukan Update(array[ j ], 1)
   
   Lebih simple kan? :v Contoh Source Code
   
   Soal yang bisa dipakai latihan :
   
   
   • SPOJ - Insertion Sort
   •  UVa - Airport Sort
   
   C. RMQ [1..K]
   
   Pada persoalan RMQ dasar, yang menjadi masalah adalah fungsi minimum dan maksimum tidak memiliki inverse. Akan tetapi, jika range pada query pasti berbentuk [1..K], persoalan ini menjadi mudah karena kita tidak memerlukan inverse, tapi ada satu ketentuan khusus, yaitu :
   
   
   • Jika query-nya maksimum, maka setiap kali kita mengubah nilai pada indeks ke-i menjadi v, maka harus berlaku array[ i ] <= v
   • Jika query-nya minimum, maka setiap kali kita mengubah nilai pada indeks ke-i menjadi v, maka harus berlaku array[ i ] >= v
   
   Sekali lagi, ini karena fungsi minimum dan maksimum tidak memiliki inverse.
   Nah, apa kegunaannya? Untuk Range Maximum Query, kita bisa menggunakannya untuk salah satu persoalan klasik, yakni Longest Increasing Subsequence atau LIS. Biasanya, kita perlu menggunakan teknik Coordinate Compression. Teknik itu kurang lebih begini :
   
   
   1. Misal ada array yang isinya 2, 5, 9, 10, 5, 6
   2. Buat array baru yang isinya sama, lalu urutkan dan buat nilainya unik. Pada kasus ini jadinya 2, 5, 6, 9, 10
   3. Ubah nilai pada array awal sesuai urutannya di array baru. Pada kasus ini jadinya 1, 2, 4, 5, 2, 3
   
   Sebelum melanjutkan, saya rasa harus dijelaskan perbedaan operasi pada BIT-nya daripada yang biasa. Pada LIS, operasi yang dilakukan bukan "Ubah nilai indeks ke-i menjadi v", namun "Ubah nilai indeks ke-i menjadi v, jika array[ i ] <= v". Kompleksitas mencari LIS dengan menggunakan BIT adalah O(N log K), di mana K merupakan banyaknya nilai berbeda pada input. Kompleksitas ini sama dengan metode greedynya. Lantas, apa keunggulannya? Perhatikan bahwa pada LIS biasa, weight (kontribusi pada total) dari tiap indeks adalah 1. Dengan menggunakan BIT, kita bisa menghitung LIS, di mana setiap indeks weightnya bisa berbeda (seperti soal UVa - Murcia's Skyline)  dalam O(N log K) !
   
   Bagaimana proses mengerjakan LIS dengan BIT? Biasanya, lakukan coordinate compression dulu. Setelah itu, proses mulai dari indeks kecil ke besar. Misal sekarang kita memproses indeks i, lakukan operasi berikut :
   
   
   • Cari label dari array[ i ], bisa dengan binary search, sebut saja idx
   • Tentukan nilai RMQ[1, idx - 1], sebut saja val
   • Tentunya, nilai LIS yang berujung di i adalah val + weight_i (biasanya 1, tapi seperti saya sebut sebelumnya bisa saja berbeda)
   • Lakukan Update(idx, val + weight_i)
   
   Setelah semua operasi dilakukan, tentu saja kita bisa menemukan LIS dengan pemanggilan Query(panjang_array_unik). Lebih mudahnya contoh soal saja ya, sekarang TLC - Brankasception .
   
   Berdasarkan deskripsi soal, jelas bahwa Tracy meminta LIS :v Akan tetapi, urutan brankas pada tiap hari bisa acak.Tentunya agar optimal, brankas kita sort perhari dulu. Setelah itu, kita gabungkan semuanya. Barulah kita cari LIS-nya. Contoh Source Code
   
   Soal yang bisa dipakai latihan :
   
   
   • TLC - Brankasception
   • SPOJ - Building Bridges(HARD)
   • UVa - Murcia's Skyline
   • UVa - Minimal Subarray Length
   
   D. BIT pada lebih dari 1 Dimensi
   
   Biasanya sih pada 2D atau 3D karena masalah memory :v Intinya sama seperti BIT biasa, cuma loopnya 2 atau 3 lapis sesuai dimensinya :v Dan loopnya pun mirip seperti BIT biasa pada 1 dimensi :v Cuma query-nya sekarang sedikit lebih ribet. Ingat prinsip inklusi-eksklusi, yang berarti pada tiap query di BIT dengan dimensi K, maka butuh mengekstrak informasi dari BIT sebanyak 2^K kali :( Contoh soal aja ya, sekarang SPOJ - Alia and Cryptography.
   
   Inti dari soal ini adalah : "Diberikan array 2 dimensi, ada 2 operasi. Yang pertama, tentukan nilai xor semua elemen array pada rentang yang diberikan. Yang kedua, ubah nilai elemen pada suatu indeks." Untuk mempermudah, sekarang anggap saja indeksnya bukan zero-based, tapi one-based ya :v
   
   Kita lihat dari operasi update terlebih dahulu. Pada kali ini, yang diminta adalah mengubah, bukan meng-xor dengan nilai sebelumnya. Dengan kata lain, kita perlu mengubah nilai pada indeks tersebut menjadi 0 dulu, baru di-xor dengan nilai barunya. Bagaimana cara mengubah nilai pada indeks tersebut menjadi 0? Kita bisa meng-xor dengan nilainya itu sendiri (ingat A xor A = 0). Persoalan update selesai.
   
   Yang kedua, untuk query. Ingat Query(x,y) akan mengembalikan nilai xor dari elemen pada persegi panjang [1..x, 1..y]. Kita bisa menggunakan inklusi eksklusi dan properti xor untuk mendapatkan hasil xor elemen pada rentang [x1..x2, y1..y2].  Contoh Source Code
   
   Soal yang bisa dipakai latihan :
   
   
   • SPOJ - Matrix Summation
   • SPOJ - Alia and Cryptography
   • PEG - IOI '07 Pairs (tipe 3)
     
2. Range Update - Point Query
   
   Sekilas mungkin kelihatan mengerikan, namun sebenarnya persoalan ini tidak sulit. Pada persoalan ini, biasanya akan diberikan query seperti berikut :
   
   
   • Tambahkan nilai pada semua indeks i, di mana a <= i <= b, sebanyak v
   • Tentukan nilai array[ i ] sekarang 
    
   Untuk menyelesaikan persoalan ini, kita gunakan BIT yang isinya sebagai Partial Difference. Untuk mempermudah, anggap array-nya one-based. Misal kita memiliki array baru untuk partial difference, maka nilai diff[ i ] = array[ i ] - array[ i-1 ]. Kurang lebih seperti ini :
   
   array : 2, 5, 10, 2, 28, 8
   diff   :  2, 3, 5, -8, 26, -20
   
   Perhatikan juga properti pada diff. Jika ingin mendapatkan nilai dari array[ i ], bisa kita dapatkan dengan menjumlahkan diff[ 1 ], diff[ 2 ], ... , dan diff[ i ] ! Properti ini akan kita gunakan dalam mengerjakan Range Update - Point Query menggunakan BIT.
   
   Misal terdapat update dari indeks a sampai b sebanyak v, apa yang terjadi pada array diff? Yang terjadi adalah :
   
   
   • diff[ a ] bertambah sebanyak v
   • diff[ b+1 ] berkurang sebanyak v
   
   Yup, hanya ini yang terjadi. Dengan kata lain, pada operasi update a b v, kita bisa melakukan 2 buah update pada BIT seperti yang saya tulis di atas. Saya jarang bertemu soal yang benar-benar perlu BIT karena yang saya temui kebanyakan operasinya offline (update semua dulu baru query). Tapi untuk pembelajaran (bukan untuk mempersulit diri ya :v), contoh soalnya SPOJ - Haybale Stacking.
   
   Pada soal ini, kita diminta melakukan operasi mengupdate indeks a sampai b sebanyak 1. Setelah itu, tentukan median dari array tersebut. Operasi update bisa dilakukan dengan BIT, dan untuk mencari median, bisa menggunakan nth_element atau sort pada STL. Karena males ngecek nth_element, saya pake sort aja :v Contoh Source Code
   
   Soal yang bisa dipakai latihan:
   
   
   • SPOJ - Update the Array!
   • SPOJ - Haybale Stacking
   • SPOJ - Air Combat
     
3. Range Update - Range Query
   
   Bisa dibilang, ini materi yang cukup gila. Menurut saya sih. Saya kurang yakin ketika menulis ini, tapi yah.. semoga saja pengalaman saya cukup benar :v
   Inti persoalan dari soal ini, misal diberi tahu bahwa nilai fungsi atau f(i) dari indeks ke-i merupakan i^k, untuk k >= 0 dan selalu tetap pada soal ini. Diberikan query seperti berikut :
   
   
   • Tambahkan nilai array[ i ],untuk semua a <= i <= b sebanyak v
   • Tentukan total array[ i ] * f(i), untuk setiap a <= i <= b (ingat penjelasan nilai fungsi sebelumnya)
   
   Untuk mengerjakan soal ini, bisa dibentuk menjadi Query(x) = m * g(x) - c, di mana g(x) merupakan f(1) + f (2) + ... + f(x). Untuk menyelesaikan ini, kita perlu mengetahui nilai m dan c. Untuk itu, kita memerlukan 2 BIT terpisah. Observasi di bawah ini untuk tiap update dalam bentuk a b v.
   
   Untuk menghitung nilai m, sebenarnya sama dengan Range Update - Point Query. Kita bisa mendapatkan observasi seperti berikut untuk setiap nilai i yang mungkin :
   
   
   • i < a, m = 0
   • a <= i <= b, m = v
   • b < i, m = 0
   
   Dengan menggunakan observasi berikut, jelas bahwa Range Update - Point Query bisa kita gunakan pada salah satu BIT.
   
   Untuk menghitung nilai c, kita perlu mengobservasi kemungkinan untuk setiap nilai i yang mungkin :
   
   
   • i < a, maka c = 0
   • a <= i <= b, maka c = v * g(a - 1)
   • b < i, c = -v * ( g(b) - g(a - 1) )
   
   Lagi-lagi, kita memerlukan Range Update - Point Query, namun pada BIT yang berbeda.
   Oiya, untuk sedikit membantu, saya tulis nilai g(x) untuk k <= 3 ya :p :
   
   
   • k = 0  -> x
   • k = 1 ->  x * (x + 1) / 2
   • k = 2 ->  x * (x + 1) * (2x + 1) / 6
   • k = 3 -> (x *(x + 1) / 2) ^ 2
   
    Sekarang, contoh soal aja ya, pakai yang mainstream, SPOJ - Horrible Queries. Permasalahan soal ini mirip yang saya jelaskan, dengan k = 0. Step-stepnya persis dengan yang saya jelaskan sebelumnya. Jadi bingung mau bahas apa :| Ya intinya seperti itu. Contoh Source Code.
   
   Perhatikan juga bahwa terkadang ada soal yang cukup ekstrim, di mana fungsinya tidak untuk 1 jenis k, namun bisa beberapa sehingga bentuknya polinom! Misalnya LA - Alien Abduction Again. Untuk mengerjakan soal ini, solusinya adalah, untuk tiap pangkat kita buat BIT penghitung m-nya masing-masing. Untuk BIT penghitung c digabung jelas gak papa. Hanya saja, codingannya cukup "nasty". Tapi saya yakin, mengerjakan soal ini bisa meningkatkan kemampuan anda!
   
   Soal yang bisa dipakai latihan :
   
   
   • SPOJ - Halt the War
   • SPOJ - Horrible Queries
   • LA - Alien Abduction Again

Penutup

Sejauh ini (versi halus dari setahun ini :v), BIT saya gunakan untuk fungsi-fungsi ini. Post ini difokuskan ke penggunaan BIT saja, tapi ingat kalau struktur data bisa di-"mix & match" seperti yang ditulis di sini. Jika ada yang ingin ditanyakan, bisa ditulis di kolom komentar, sebisa mungkin akan saya jawab :) Kritik dan saran sangat saya nantikan :)