Manipulasi Segmen pada BIT & Segment Tree

Kali ini saya akan berbagi suatu teknik yang lucu, yaitu mengoprek "jeroan" segment tree dan BIT. Kadang-kadang, dengan mengetahui struktur dalam suatu objek dan langsung memanipulasinya, kita bisa melakukan berbagai hal dengan lebih efisien. Misalnya kalau Anda paham struktur dalam televisi, mungkin Anda bisa mengatur supaya televisinya otomatis mati pada jam-jam tertentu.

Saya akan memberikan beberapa contoh yang umum.

Contoh umum

Misalkan diberikan soal:
Terdapat sebuah array A yang awalnya kosong dan N operasi, yang bisa berupa:

1. tambah x, artinya tambahkan x ke dalam array A. Dijamin tidak nilai-nilai di dalam array A akan selalu unik
2. tanya k, artinya cetak bilangan terkecil ke-k di dalam array A pada saat itu

Batasan:

1. 1 ≤ N ≤ 100.000
2. Pada setiap operasi tambah, 1 ≤ x ≤ N
3. Pada setiap operasi tanya, 1 ≤ k ≤ N

Salah satu cara yang mungkin langsung terpikir adalah dengan BST. Namun BST relatif sulit untuk di-coding, lagipula tidak ada operasi menghapus. Oleh karena itu, marilah kita coba kerjakan dengan segment tree.

Karena setiap bilangan yang diberikan selalu positif dan tidak lebih dari 100.000, kita bisa siapkan sebuah range sum query (misalnya namanya sum). Penyelesaiannya:

1. Jika ada operasi tambah x, tambahkan sum[x] dengan 1
2. Jika ada operasi tanya k, cari indeks j, supaya sum[1] + sum[2] + sum[3] + ... + sum[j-1] = k-1, dan jawabannya adalah j. Mengapa hal ini benar? Karena kita mencari suatu bilangan j, yang banyaknya bilangan sebelum bilangan j ada sebanyak k-1. Artinya j merupakan bilangan terkecil ke-k

Dalam implementasinya:

1. Jika ada operasi tambah x, update indeks ke-x dengan menambahkan 1. Dengan segment tree, kompleksitasnya O(log N)
2. Jika ada operasi tanya k, binary search nilai j, hitung sum[1] + sum[2] + sum[3] + ... + sum[j-1], misalkan nilainya S. Jika S ≤ k-1, artinya j harus lebih besar. Jika S > k-1, artinya j harus lebih kecil. Kompleksitas binary search adalah O(log N), dan setiap kali menebak nilai j, dilakukan query pada segment tree sebesar O(log N). Jadi kompleksitas menjawab pertanyaan adalah O(log² N).

Tidak terlalu buruk, seharusnya cukup cepat untuk nilai N ~ 100.000.
Namun, sebenarnya kita bisa melakukannya dengan lebih baik.

Perhatikan contoh berikut. Misalnya nilai A saat ini [1, 3, 4, 6, 7]. Bentuk segment tree yang kita punya adalah:

Untuk mencari bilangan terbesar ke-3, kita bisa mulai dari root. Informasi pada root menyatakan bahwa terdapat 5 bilangan yang dicakup segmen ini, ke kiri ada 2 bilangan, dan ke kanan ada 3 bilangan. Berhubung kita sedang mencari bilangan terkecil ke-3, jelas menelusuri segmen kiri tidak ada gunanya (hanya ada 2 bilangan di sana!). Dengan demikian, kita turun ke segmen kanan. Pada segmen ini, tujuan kita bukan lagi mencari bilangan terkecil ke-3, melainkan mencari bilangan terkecil ke-1. Segmen ini mencakup 3 bilangan, ke kiri ada 1 bilangan, dan ke kanan ada 2 bilangan. Karena kita ingin mencari bilangan terkecil ke-1, kita bisa mengunjungi segmen kiri. Ulangi terus hal ini, dan akhirnya kita akan sampai pada leaf node yang mencakup jawaban kita, yaitu 4.

Berapa kompleksitas untuk penelusuran ini? O(log N)! Kini untuk N ~ 1.000.000 juga masih cukup kuat.

Bagaimana jika kita ingin menerapkan teknik ini pada BIT? Tidak masalah, yang penting kita paham bagaimana struktur BIT. Untuk contoh di atas, struktur BIT yang kita miliki adalah:

Jika dilihat lebih jauh, sebenarnya BIT bisa dipandang sebagai:

Persis seperti segment tree! Jadi teknik penelusuran untuk mencari bilangan terkecil ke-k juga bisa dilakukan pada BIT.

Contoh tidak umum

Baru-baru ini saya menggunakan teknik manipulasi segmen untuk soal Codeforces - CGCDSSQ. Cukup terharu karena mendapatkan accepted :')

Inti soal:
Diberikan sebuah array A berisi N bilangan. Jika diberikan sebuah bilangan v, berapa banyak i dan j (1 ≤ i ≤ j ≤ N) yang nilai GCD(A[i], A[i+1], A[i+2], ..., A[j]) = v? (demi kemudahan, pertanyaan ini akan disebut sebagai "query v")

Batasan:

1. N ~ 100.000
2. A[i] ~ 1.000.000.000

Soal ini tidak memiliki operasi update pada suatu elemen, sehingga saya mencoba menyelesaikannya dengan pendekatan offline query (seluruh query disimpan dulu, diproses, baru dicari jawabannya). Jawaban untuk pertanyaan berapa banyak i dan j (1 ≤ i ≤ j ≤ N) yang nilai GCD(A[i..j]) = v akan disimpan dalam array bernama ans[v]. Berhubung nilai v bisa sangat besar, maka dapat digunakan pemetaan atau struktur data map pada C++.

Observasi 1:
Untuk i adalah suatu bilangan yang tetap dan j adalah bilangan yang berada di antara (i ≤ j ≤ N-1), selalu dipenuhi GCD(A[i..j]) ≥ GCD(A[i..j+1]). Buktinya sederhana, karena nilai GCD-nya tidak akan bertambah seiring dengan semakin besarnya j. Adanya malah berkurang.

Observasi 2:
Untuk i adalah suatu bilangan yang tetap dan j adalah bilangan yang berada di antara (i ≤ j ≤ N-1), hanya ada maksimal 30 nilai j yang mengakibatkan GCD(A[i..j]) > GCD(A[i..j+1]). Bukti: kejadian GCD(A[i..j]) > GCD(A[i..j+1]) hanya terjadi jika terdapat pengurangan faktor dari GCD(A[i..j]) ke GCD(A[i..j+1]). Karena nilai pada A tidak lebih dari 1.000.000.000, berapa banyak faktor maksimal yang bisa dimiliki? Tidak mungkin lebih dari 30! Observasi ini juga memberikan informasi bahwa hanya ada 30 * 100.000 nilai GCD yang mungkin.

Berdasarkan observasi tersebut, kita bisa mengenumerasi seluruh kemungkinan GCD (paling banyak 30 * 100.000), lalu mencatat banyaknya pasangan (i, j) yang menghasilkan nilai GCD tersebut secara efisien. Bagiamana caranya?

Observasi 3:
Jika diketahui GCD(A[i..j]) = x, GCD(A[i..j]) = GCD(A[i..k]), dan GCD(A[i..j]) ≠ GCD(A[i..k+1]), maka diketahui bahwa ada (k-j+1) nilai berbeda untuk r, sedemikian sehingga GCD(A[i..r]) bernilai x.

Kita bisa mencoba seluruh kemungkinan i, lalu mencari seluruh kemungkinan j yang mengakibatkan GCD(A[i..j]) > GCD(A[i..j+1]), paling banyak ada 30 nilai j yang berbeda). Misalkan nilai-nilai j tersebut ditampung dalam array bernama S. Berdasarkan Observasi 3, untuk setiap x yang mungkin, tambahkan ans[GCD(A[i..S[x]])] dengan (S[x+1] - S[x]).

Karena mungkin sulit dipahami (saya pun sulit mengetikkannya), berikut ini adalah contohnya. Misalkan i = 1, lalu:

• A[1] = 12
• A[2] = 60
• A[3] = 36
• A[4] = 16
• A[5] = 20
• A[6] = 8
• A[7] = 18

Maka didapatkan S = [3, 6, 7], karena:

• GCD(A[1..3]) ≠ GCD(A[1..4]) (yaitu 12 dan 4)
• GCD(A[1..6]) ≠ GCD(A[1..7]) (yaitu 4 dan 2)
• GCD(A[1..7]) ≠ GCD(A[1..8]) (yaitu 4 dan <tidak terdefinisi>)

Kemudian:

• ans[12] bertambah 3, karena pasangan (1, 1), (1, 2), (1, 3) memiliki GCD bernilai 12
• ans[4] bertambah 3, karena pasangan (1, 4), (1, 5), (1, 6) memiliki GCD bernilai 4
• ans[2] bertambah 1, karena pasangan (1, 7) memiliki GCD bernilai 2

Lanjutkan untuk i = 2, i = 3, dan seterusnya hingga i = 7. Kita akan mendapatkan array ans[x] yang sudah menyimpan jawaban untuk
"query x".

Nah kita kembali ke algoritmanya. Berikut ini rancangan algoritma yang bisa digunakan:

for i <- 1..N
  j <- i
  while (j < N)
    k <- next(j)
    tambahkan ans[GCD(A[i..j])] dengan (k - j + 1)
    j <- k     

Untuk mempercepat perhitungan GCD(A[i..j]), bisa dibuat segment tree. Kini perhitungan tersebut bisa dilakukan dalam O(log N).

Fungsi next(j) adalah fungsi untuk mendapatkan nilai x berikutnya yang mengakibatkan GCD(A[i..x]) > GCD(A[i..x+1]) dan x lebih besar dari j. Implementasi fungsi ini bisa dengan binary search + query GCD, sehingga kompleksitasnya O(log²N) per pemanggilan fungsi. Tunggu dulu, O(log²N) per pemanggilan fungsi next(j)? Pemanggilan fungsi next(j) maksimal dilakukan 30 kali, jadi kompleksitas akhirnya O(N log²N * 30)?!? Jelas terlalu lambat untuk accepted!

Di sini kita bisa memainkan segmen-segmen dalam segment tree yang sudah ada. Saya menghilangkan binary search pada fungsi next(j) dengan algoritma "naik gunung turun gunung". Idenya adalah, untuk mencari nilai next(j), kita mulai dari posisi j, lalu berusaha memperlebar jangkauan ke kanan dengan cara ke atas, lalu turun ke arah sekanan mungkin. Perhatikan gambar berikut:

Misalkan i = 1 dan j = 1. Kita tertarik untuk mencari nilai next(1), kita perluas jangkauan (ke kanan) selama nilai GCD yang kita cakup masih sama dengan 12. Hingga suatu titik, ternyata kita tidak bisa lagi memperluas jangkauan. Dengan demikian, kita coba perkecil jangkauan hingga didapatkan batas yang pasti. Panah biru pada gambar di atas menyatakan titik terjauh nilai GCD(A[i..x]) masih bernilai 12. Cara ini memiliki kompleksitas O(log N), karena dalam sekali pemanggilan fungsi next, proses "naik gunung" maksimal dilakukan O(log N) kali dan "turun gunung" maksimal dilakukan O(log N) kali juga.

Jika dipanggil next lagi, cara serupa diulang, dan kita akan mendapatkan batas akhir nilai GCD(A[i..x]) bernilai 6.

Jika dipanggil sekali lagi, kita mendapatkan batas akhir nilai GCD(A[i..x]) bernilai 2. Kebetulan, sudah dicapai batas akhir. Kini saatnya nilai i dirubah menjadi i+1, j menjadi i+1, dan proses ini diulang kembali.

Solusi ini benar-benar indah, dan saya terharu ketika memprogramnya. Berikut adalah implementasi dalam C++: