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.

Oh ya, sebenarnya soal ini adalah penyederhanaan dari soal SPOJ HORRIBLE.

---

Penggunaan Lazy Propagation?

Dengan struktur BIT, penggunaan lazy propagation agak sulit dilakukan. Alasannya karena untuk melakukan "propagate", diperlukan kompleksitas O(log N). Sebab banyaknya segmen yang berada di bawah suatu segmen pada BIT adalah O(log N). Bandingkan dengan segment tree yang operasi "propagate" dapat dilakukan dalam O(1), berhubung banyaknya segmen di bawah suatu segmen selalu 2.

Terdapat suatu cara untuk menggunakan lazy propagation di BIT, yaitu dengan membuat BIT 1 lagi untuk mengisi "keompongan" struktur BIT (lihat bagian bonus pada pembahasan BIT). Hari ini saya tidak membahas teknik ini.

Strategi penyelesaian yang akan dibahas tidak menggunakan lazy propagation, melainkan dengan permodelan BIT untuk penjumlahan fungsi.

---

Solusi dengan 2 BIT

Secara umum, solusi ini dapat digunakan apabila:

1. Elemen ke-i pada array dapat dinyatakan dalam f(i), dengan f(x) = k_xx^p untuk suatu nilai p yang tetap dan variabel k_x.
2. Operasi yang diperlukan adalah:
1. Penambahan/pengurangan nilai variabel k_a, k_a+1, k_a+2, ..., k_b dengan suatu konstanta v, untuk suatu a dan b.
2. Pencarian nilai f(1)+f(2)+...+f(x), untuk suatu x.

Soal yang kita hadapi memenuhi syarat-syarat tersebut. Dalam kasus ini, p dapat dianggap 0. Jadi f(x) = k_x, yang mana nilai k_x sewaktu-waktu ditambah/dikurangi dengan operasi add(a, b, v). Juga dilakukan pencarian f(1)+f(2)+...+f(x), yang merupakan operasi sum(x).

Solusi ini menggunakan 2 struktur array, akan saya sebut arrK dan arrN. arrK akan menyimpan nilai k, dan arrN menyimpan konstanta normalisasi.

Sebagai contoh, perhatikan apa yang terjadi ketika dilakukan add(a, b, v):

Struktur ini dapat diuraikan menjadi 2 grafik:

Pada kasus tersebut, arrK akan bernilai:

• 0, jika x < a
• v, jika a ≤ x ≤ b. Perhatikan bahwa yang disimpan adalah "gradien", jadi nilainya selalu v.
• 0, jika x > b

Sementara itu arrN akan bernilai:

• 0, jika x < a
• -(a-1)*v, jika a ≤ x ≤ b
• b*v - (a-1)*v, jika x > b

Untuk mencari sum(x), caranya adalah: arrK[x]*x + arrN[x].

Sampai saat ini, sangat semuanya terlihat tidak masuk akal. Untuk memahami bagaimana cara kerjanya, perhatikan 3 kasus yang mungkin untuk nilai x. Asumsikan sebelumnya telah dilakukan satu kali add(a, b, v).

1. Jika x < a, maka sum(x) = 0
2. Jika a ≤ x ≤ b, maka sum(x) = x*v - (a-1)*v
3. Jika x > b, maka sum(x) = b*v - (a-1)*v

Penjelasan untuk masing-masing kasus dapat dilihat pada ilustrasi berikut:

Lalu bagaimana apabila telah dilakukan beberapa kali operasi add(a, b, v)? Pada kenyataannya, operasi-operasi add tidak mempengaruhi satu sama lain. Kita tetap dapat mencari sum(x) dengan arrK[x]*x + arrN[x].

Memang jika hanya diperhatikan dari sisi arrK, nilai yang kita miliki tidak masuk akal. Namun ingat bahwa semua operasi yang dilakukan pada indeks sebelum x telah "dinormalisasi" oleh arrN.

Anda dapat menganggap bahwa arrK menyimpan nilai k yang aktif, dan arrN menyimpan konstanta normalisasi untuk operasi-operasi add yang telah dilakukan.

Untuk mengimplementasikan solusi ini pada BIT, kita dapat membuat 2 BIT yang masing-masing merepresentasikan nilai arrK dan arrN. Sebut saja bitK dan bitN adalah kedua BIT tersebut.

Jadi untuk setiap add(a, b, v), lakukan:

1. update(bitK, a, v)
2. update(bitK, b+1, -v)
3. update(bitN, a, (a-1)*v)
4. update(bitN, b+1, b*v)

Kemudian setiap query(x) dapat dijawab dengan: query(bitK, x)*x + query(bitN, x).

---

Implementasi

Seperti biasa, implementasi dengan BIT ini sangat mudah ditulis. Berikut adalah solusi untuk soal SPOJ HORRIBLE. Perhatikan bahwa query sum pada soal ini adalah pencarian jumlahan dari suatu rentang a sampai b, yang tentunya dapat dengan mudah didapatkan dengan sum(b)-sum(a-1).

---

Generalisasi

Untuk soal yang lebih dekat dengan Alien Abduction Again, kini operasi yang ada dimodifikasi menjadi:

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. (tidak ada perubahan)
2. sum(x), artinya cari nilai 1*A[1]+2*A[2]+3*A[3]+...+x*A[x].

Terlihat jelas bahwa elemen ke-i pada array tersebut dapat dinyatakan dalam f(i), dengan f(x) = k_xx¹. Perhatikan apa yang terjadi ketika dilakukan add(a, b, v):

Struktur ini dapat diuraikan menjadi 2 grafik:

Pada kasus tersebut, arrK akan bernilai:

• 0, jika x < a
• v, jika a ≤ x ≤ b
• 0, jika x > b

Sementara itu arrN akan bernilai:

• 0, jika x < a
• -(1v + 2v + 3v + ... + (a-1)v), jika a ≤ x ≤ b
• (1v + 2v + 3v + ... + bv) - (1v + 2v + 3v + ... + (a-1)v), jika x > b

Untuk mencari sum(x), caranya adalah: arrK[x]*(1 + 2 + 3 + ... + x) + arrN[x].

Coba pahami penguraian grafik pada gambar di atas untuk memahami bagaimana strategi ini bisa benar.

Cara ini juga bekerja untuk sembarang nilai p. Mari kita modifikasi operasi sum menjadi:
sum(x), artinya cari nilai 1²A[1]+2²A[2]+3²A[3]+...+x²A[x].

Kali ini elemen ke-i pada array tersebut dapat dinyatakan dalam f(i), dengan f(x) = k_xx². Ketika dilakukan add(a, b, v), arrK akan bernilai:

• 0, jika x < a
• v, jika a ≤ x ≤ b
• 0, jika x > b

Sementara itu arrN akan bernilai:

• 0, jika x < a
• -(1²v + 2²v + 3²v + ... + (a-1)²v), jika a ≤ x ≤ b
• (1²v + 2²v + 3²v + ... + b²v) - (1²v + 2²v + 3²v + ... + (a-1)²v), jika x > b

Untuk mencari sum(x), caranya adalah: arrK[x]*(1² + 2² + 3² + ... + x²) + arrN[x].

---

Generalisasi Tingkat Tinggi

Lebih jauh lagi, solusi ini dapat digunakan untuk sembarang fungsi. Tidak harus memenuhi bentuk f(x) = k_xx^p, melainkan dapat berupa f(x) = k_xg(x), dengan g(x) adalah sembarang fungsi dengan parameter x.

Ketika dilakukan add(a, b, v), arrK akan bernilai:

• 0, jika x < a
• v, jika a ≤ x ≤ b
• 0, jika x > b

Sementara itu arrN akan bernilai:

• 0, jika x < a
• -(g(1)v + g(2)v + g(3)v + ... + g(a-1)v), jika a ≤ x ≤ b
• (g(1)v + g(2)v + g(3)v + ... + g(b)v) - (g(1)v + g(2)v + g(3)v + ... + g(a-1)v), jika x > b

Untuk mencari sum(x), caranya adalah: arrK[x]*(g(1) + g(2) + g(3) + ... + g(x)) + arrN[x].

Supaya lebih ringkas, saya akan menuliskannya dalam notasi sigma.

Ketika dilakukan add(a, b, v), \(arrK\) akan bernilai:

• \(0\), jika \(x \lt a\)
• \(v\), jika \(a \le x \le b\)
• \(0\), jika \(x \gt b\)

Sementara itu \(arrN\) akan bernilai:

• \(0\), jika \(x \lt a\)
• \(\displaystyle -v\sum_{i=1}^{a-1} g(i)\), jika \(a \le x \le b\)
• \(\displaystyle v\sum_{i=1}^{b} g(i)-v\sum_{i=1}^{a-1} g(i)\), jika \(x \gt b\)

Untuk mencari sum(x), caranya adalah: \(\displaystyle arrK[x]\left(\sum_{i=1}^{x} g(i)\right) + arrN[x]\).

Inilah yang disebut Aji sebagai "Magic BIT". Bagian \(\displaystyle \sum_{i} g(i) \) ia sebut sebagai "konstanta magic". Konstanta ini dapat di-precompute, karena hanya ada O(N) kemungkinan nilai.

Semua ini memang sangat gila, tetapi masuk di akal apabila dicerna. Pengalaman saya sendiri, memahaminya dengan menganalisis grafik yang telah diuraikan membantu dalam pemahaman.

---

Latihan

Seluruh ilmu ini harus diterapkan pada latihan, supaya terasa dan teruji pemahamannya.

• SPOJ HORRIBLE
• SPOJ RPAR
• Alien Abduction Again (LA 6443)

---

Penutup

Tidak perlu terburu-buru dalam memahami semua ini. Coba dicerna sedikit demi sedikit, sampai Anda mendapatkan intinya.

Memahami teknik ini mungkin tidak seberapa berharga, dan kecil kemungkinan soal sejenis ini akan dikeluarkan lagi. Tapi siapa tahu? ACM ICPC adalah hutan hujan yang gelap, entah hewan buas apa yang ada di depan nantinya. Semoga bermanfaat!