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.

Untuk kasus x berada di posisi lainnya, ternyata dibutuhkan 7 langkah.

Cerita soal ini memang tidak masuk akal, tetapi biarlah yang penting intinya tersampaikan. Sebenarnya ini adalah soal Surveillance - ACM ICPC World Final 2014 yang disederhanakan konstruksi graph-nya.

Soal ini dapat diselesaikan menggunakan binary search the answer. Misalnya ditebak diperlukan K kali perpindahan. Berikutnya cukup coba lakukan "fast-forward" sebanyak K kali dari posisi x, dan periksa apakah sudah mengitari lingkaran. Apabila sudah, berarti K mungkin dapat diperkecil. Sebaliknya, bila belum, berarti K perlu diperbesar.

Nilai K terbesar yang mungkin adalah sebanyak N+1, sehingga diperlukan O(log N) tebakan. Untuk setiap tebakan, dibutuhkan O(log N) untuk melakukan fast-forward. Jadi kompleksitas menjawab pertanyaan untuk suatu posisi berdiri awalnya adalah O(log² N).

Cukup cepat? Ya, jika hanya 1 posisi berdiri yang dipertanyaan. Apabila kita diminta mencetak jawaban untuk semua kemungkinan posisi awal berdiri, berarti kompleksitasnya O(N log² N). Untuk N mencapai jutaan, kompleksitas ini berisiko untuk TLE.

---

Observasi

Perhatikan beberapa aktivitas pertama pada binary search. Misalnya N = 15, berarti banyaknya lompatan yang perlu dilakukan ada di antara 1 sampai 16.

Dengan binary search, pertama ditebak K=8, lakukan fast forward untuk 8 lompatan, periksa jawabannya. Berikut ilustrasinya. Untuk mempermudah, saya hanya menggambar batu yang dapat dikunjungi jika perjalanan dimulai dari x.

Apabila gagal, K dinaikkan menjadi 12, lalu lakukan fast forward untuk 12 lompatan, periksa jawabannya.

Terlihat adanya redundansi. Untuk fast forward 12 lompatan, dilakukan lompatan untuk 8 + 4. Sebelumnya kita sudah tahu di mana posisi ketika dilakukan 8 lompatan. Alangkah baiknya bila kita cukup meneruskan perjalanan dari posisi yang telah ditemukan itu, yaitu dengan melangkah 4 lompatan.

Bagaimana apabila berhasil? K perlu diturunkan menjadi 4, lalu fast forward untuk 4 lompatan, dan periksa jawabannya. Dalam kasus ini, tidak ada redundansi.

Ternyata redundansi hanya terjadi apabila tebakan gagal. Untuk kasus terburuk, redundansi terbanyak terjadi ketika seluruh percobaan tebakan gagal. Berarti aktivitas lompatan yang dilakukan untuk tebak-tebakan adalah:

1. 8
2. 8 + 4
3. 8 + 4 + 2
4. 8 + 4 + 2 + 1

Sampai saat ini, jawaban pasti telah ditemui. Bila tebakan ke-4 masih gagal, artinya dibutuhkan 16 lompatan. Bila Anda bayangkan bentuk di atas seperti separuh matriks yang banyaknya baris dan kolomnya adalah log N, maka banyaknya elemennya ada O(log² N). Dengan kata lain, kompleksitas solusi ini O(log² N).

Terlihat bahwa redundansi ini cukup boros, banyak operasi yang diulang-ulang. Apabila kita menggunakan posisi hasil fast forward sebelumnya, hasilnya menjadi jauh lebih baik:

1. 8
2. 8 + 4
3. 8 + 4 + 2
4. 8 + 4 + 2 + 1

Kini yang kita dapatkan hanya diagonal matriksnya saja, sebesar O(log N). Jadi optimisasi ini mampu memangkas O(log² N) menjadi O(log N).

Bagaimana bila kasusnya selang-seling, tebakannya kadang berhasil kadang gagal? Tidak masalah, redundansi yang dihemat tetap banyak. Misalnya:

1. 8 (gagal)
2. 8 + 4 (berhasil)
3. 8 + 2 (gagal)
4. 8 + 2 + 1 (tidak penting)

Ilustrasi berikut menunjukkan lompatan-lompatan yang dilakukan selama tahapan-tahapan binary search:

Anda dapat bayangkan seberapa besar efek optimisasi ini ketika tebakan maksimal yang diperlukan besar, misalnya 20 kali tebakan.

---

Implementasi

Untuk implementasi, saya suka untuk tidak menuliskan binary search pada umumnya, yang menggunakan variabel batas kiri dan batas kanan. Kali ini, binary search langsung "ditembak" dengan angka 2^p-1 terkecil yang lebih dari atau sama dengan N, lalu menurun sampai 1. Misalnya pada contoh di atas, N = 15, berarti p = 4. Berarti tembak dari 8, 4, 2, lalu 1.

Awalnya posisi kita berada di x. Ketika tebakan untuk lompat sebanyak 8 kali gagal, update posisi dengan posisi yang baru dan tambahkan jawaban sebanyak 8. Sebaliknya, tidak perlu update posisi dan berharap pada tebakan berikutnya (yaitu 4 lompatan), mengitari lingkaran masih bisa dicapai.

Implementasi ini secara mengejutkan sama sekali tidak terlihat seperti binary search:

---

Penutup

Untuk setiap struktur data Sparse Table yang Anda buat, Anda dapat menggunakan optimisasi binary search ini. Bila Anda ingat penjelasan saya tentang Lowest Common Ancestor (LCA) pada tulisan sebelumnya, teknik ini dapat digunakan sehingga kompleksitas pencarian LCA dari dua node pada tree adalah O(log N).