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.

---

Diskusi

Mungkin Anda terpikir solusi menggunakan cycle finding untuk soal ini. Sebab jika Anda perhatikan, struktur oper-mengoper ini pada akhirnya akan membentuk siklus. Namun kompleksitas pencarian solusi untuk suatu masalah tetap saja dibatasi dengan O(N).

Sekarang coba bayangkan bila untuk setiap orang ke-i, kita memiliki informasi siapa yang akan menerima bola pada putaran ke \(2^{j}\), untuk \(j \ge 0 \). Sebut saja informasi ini dengan next[i][j].

(untuk mempermudah, saya buat orang-orang yang oper-mengoper ini posisinya berderet)

Tabel next[][] memiliki ukuran \(N \times \log{N}\) (log berbasis 2).

Untuk mencari siapa yang menerima bola pada putaran ke-4 bila saat ini bola berada di orang ke-A, kita cukup mengembalikan nilai dari next[A][2].

Bagaimana untuk kasus yang sama, tetapi pada putaran ke-6? Sebelumnya kita telah mengetahui untuk jawaban putaran ke-4, yaitu next[A][2]. Sebut saja orang ini adalah orang ke-B. Permasalahan yang dihadapi kini menjadi mencari putaran ke-2, bila saat ini bola berada di orang ke-B. Jawaban akhirnya adalah next[B][1], atau bila nilai B dibuka, next[next[A][2]][1].

Strategi ini dapat digeneralisasi: untuk mencari siapa yang memegang bola pada putaran ke-Y, caranya:

1. Nyatakan Y dengan penjumlahan dari bilangan \(2^k\). Misalnya jika Y = 25, maka Y = \(2^0 + 2^3 + 2^4\)
2. Untuk setiap bilangan \(2^k\) hasil penguraian dari Y, lakukan:
1. Misalkan yang sedang memegang bola saat ini adalah orang ke-A (untuk pertama kali, A = X).
2. Ganti orang yang sedang memegang bola menjadi next[A][k]

Dapat diamati bahwa untuk sembarang X dan Y, pencarian jawaban dapat dilakukan dengan mengakses elemen tabel next[][] paling banyak O(log N) kali. Nilai O(log N) didapat dari fakta bahwa untuk menyusun suatu bilangan Y, hanya diperlukan paling banyak O(log N) bilangan \(2^k\). Kini pencarian jawaban menjadi sangat efisien!

---

Implementasi

Membentuk tabel next[][] dapat dilakukan dengan pemrograman dinamis. Perhatikan bahwa nilai next[i][j] = next[next[i][j-1]][j-1].

\(\displaystyle
next[i][j] = \left\{
\begin{array}{ll}
p[i] &, j = 0 \\
next[next[i][j-1]][j-1] &, j > 0
\end{array} \right. \)

Pengisian tabel ini dapat dilakukan dalam O(N log N).

Lalu untuk menjawab pertanyaan, cara yang saya sukai adalah menggunakan manipulasi bit:

Dari kode tersebut, terlihat lebih jelas bahwa kompleksitas solusi ini adalah O(log N) per pertanyaan.

---

Nama struktur data?

UPDATE: Berdasarkan informasi dari komentar Galangkangin Gotera, nama struktur data ini di sumber lainnya adalah sparse table.

Sebelumnya saya tidak tahu, dan sering saya sebut "fast forwarding". Alasannya karena mirip dengan fast-forward pada VCD/DVD player, yang hanya dapat mempercepat 2x, 4x, 8x, 16x, 32x (bilangan dua pangkat). Alasan lainnya adalah ketika mengimplementasikannya, saya sering menggunakan operator bit shift (<< atau >>), yang mirip dengan tombol fast-forward pada VCD/DVD player.

Operasi untuk memajukan suatu informasi juga biasa saya sebut "fast-forward".

---

Penggunaan

Seperti yang saya sebut sebelumnya, struktur data ini digunakan pada pencarian LCA dan RMQ.

LCA (Lowest Common Ancestor)

Diberikan sebuah rooted tree dan dua node, misalnya A dan B, cari node pertama yang merupakan leluhur dari A dan B. Nilai p[i] untuk penjelasan pada tulisan ini dapat diganti maknanya menjadi orang tua dari node ke-i. Ketika diberikan dua node, misalnya A dan B, pertama samakan dulu kedalaman dari node A dan node B. Anggap node A lebih dalam 75 tingkat dari node B. Berarti Anda cukup "fast-forward" A ke parent-ke-75-nya. Setelah kedalamannya sama, lakukan binary search untuk menebak suatu angka X, apakah LCA A dan B berada di tingkat ke-X di atas mereka.

• Bila nilai parent ke-X dari A dan B sama, berarti dipastikan LCA dari A dan B berada di ketinggian yang ≤ X.
• Bila nilai parent ke-X dari A dan B berbeda, berarti dipastikan LCA dari A dan B berada di ketinggian yang > X.

Menggunakan solusi ini, kompleksitasnya adalah O(log N + log² N). Kuadrat dari log N didapat dari diperlukan O(log N) tebakan untuk X, dan untuk setiap pemeriksaan diperlukan O(log N) untuk melakukan fast forward. Terdapat teknik khusus binary search yang memungkinkan seluruh proses binary search + fast forward ini menjadi O(log N) saja, sehingga solusi akhirnya adalah O(log N). Suatu saat nanti akan saya jelaskan.

RMQ (Range Minimum/Maximum Query)

Anggap yang kali ini hendak dicari adalah Range Minimum Query.
Diberikan sebuah array bernama arr, dan sejumlah pertanyaan berbunyi "dari posisi ke-i sampai ke-j, berapa nilai yang paling kecil?"

Solusi menggunakan Sparse Table agak unik. Sekarang misalkan pertanyaannya berbunyi: "dari posisi ke-i sampai dengan posisi ke-(i + 2^k), berapa nilai yang paling kecil?

Solusinya adalah Anda dapat memodifikasi makna next[i][j] menjadi nilai terkecil dari posisi ke-i sampai dengan posisi ke-(2^j). Sehingga rumus dapat diubah menjadi:

\(\displaystyle
next[i][j] = \left\{
\begin{array}{ll}
arr[i] &, j = 0 \\
min(next[i][j-1], next[i + 2^{j-1} - 1][j-1]) &, j > 0
\end{array} \right. \)

Hati-hati dengan index out of bound pada ekspresi \(i + 2^{j-1} - 1\).
Kini jawaban dapat dicari dengan "fast forwarding" untuk setiap 2^k, sehingga kompleksitas solusinya adalah O(log N).

Terdapat cara yang memungkinkan proses pencarian jawaban adalah O(1). Mungkin akan saya jelaskan suatu saat nanti, atau bila Anda penasaran silakan coba dipikirkan sendiri.

---

Penutup

Pengetahuan ini mungkin "underrated", jarang dikemukakan padahal sangat bermanfaat. Semoga bekal pengetahuan Anda bertambah.

Sebagai latihan, Anda dapat coba mengerjakan Surveillance - ACM ICPC World Final 2014. Tidak perlu khawatir dengan judul "world final".