Fixed Size RMQ

Pada kesempatan kali ini saya ingin memperkenalkan struktur data yang saya pelajari dari Brian Marshal. Entah apa nama struktur data ini, sehingga akan saya sebut sebagai "fixed segment array" saja. Struktur data ini bisa jadi sangat membantu dalam optimisasi algoritma, misalnya pada DP. Simak penjelasan berikut dan cobalah untuk mengerjakan soalnya :)

---

Permasalahan

Diberikan sebuah array bernama A yang berisi N bilangan, dan sebuah bilangan L. Terdapat Q buah pertanyaan yang berbunyi:
Dari indeks X sampai indeks X+L-1, bilangan apa yang paling kecil?

Sepintas, persoalan ini sangat mirip dengan RMQ (Range Minimum Query). Oleh karena itu, struktur data seperti segment tree atau sparse table seharusnya dapat melayani pertanyaan-pertanyaan tersebut dengan efisien.

Struktur data	Kompleksitas membangun	Kompleksitas per pertanyaan
Segment tree	O(N)	O(log N)
Sparse table	O(N log N)	O(1)

Namun, solusi dengan struktur data tersebut terlalu overkill. Perhatikan bahwa terdapat karakteristik khusus pada masalah di atas, yaitu besar rentang yang diberikan selalu L. Ada struktur data yang lebih efisien untuk menyelesaikannya, yaitu fixed segment array. Kompleksitas untuk membangunnya hanya O(N) dan setiap pertanyaan dapat dijawab dalam O(1).

---

Ide Utama

Bilangan-bilangan dipartisi menjadi beberapa subarray yang besarnya L. Untuk subarray yang besarnya lebih kecil dari L, tambahkan beberapa elemen dummy. Untuk kasus ini, bisa diisi dengan bilangan yang sangat besar (INF). Untuk setiap indeks ke-i, kita simpan dua nilai:

1. prev[i], menyimpan nilai terkecil dari A[i], A[i-1], ... (sampai pada pembatas pertama yang ditemui).
2. next[i], menyimpan nilai terkecil dari A[i], A[i+1], ... (sampai pada pembatas pertama yang ditemui).

Misalkan L = 3, perhatikan gambar berikut:

isi array prev ditandai dengan warna biru, dan next dengan warna hijau. Berikut beberapa penjelasannya:

1. prev[1] menyimpan min(A[1]), next[1] menyimpan min(A[1], A[2], A[3]).
2. prev[2] menyimpan min(A[1], A[2]), next[2] menyimpan min(A[2], A[3]).
3. prev[3] menyimpan min(A[1], A[2], A[3]), next[3] menyimpan min(A[3]).
4. prev[5] menyimpan min(A[4], A[5]), next[5] menyimpan min(A[5], A[6]).

Cara mencari bilangan terkecil dari indeks X sampai indeks X+L-1 dapat dilakukan dengan mudah, yaitu cukup kembalikan min(next[X], prev[X+L-1]). Perhatikan gambar berikut untuk memahami mengapa hal itu benar:

Untuk gambar pertama, mencari min(A[2], A[3], A[4]) dapat dilakukan dengan memeriksa next[2] atau prev[4] yang lebih kecil. Secara bersamaan, next[2] sudah mewakili min(A[2], A[3]), dan prev[4] mewakili min(A[4]). Sehingga kita cukup membandingkan kedua nilai tersebut! Perhatikan gambar berikutnya untuk lebih jelasnya.

---

Analisis Kompleksitas

Mengisi array prev dan next dapat dilakukan dengan dua kali looping: sekali dari kiri ke kanan (mengisi array prev), dan sekali dari kanan ke kiri (mengisi array next). Sehingga kompleksitas membangunnya adalah O(N).

Untuk menjawab pertanyaan, dilakukan cukup dengan membandingkan dua nilai. Dengan demikian, kompleksitasnya O(1)!

---

Generalisasi

Untuk dimensi yang lebih tinggi (misalnya dalam matriks), struktur data ini juga bisa digunakan. Bedanya, Anda perlu melakukan prekomputasi yang lebih banyak, bukan sekedar prev dan next saja. Contohnya untuk matriks, Anda perlu membuat 4 tabel. Silakan dipikirkan bagaimana caranya dan bila ada pertanyaan, silakan tinggalkan komentar :)

---

Penutup

Implementasi struktur data ini sangat mudah. Saya merekomendasikan Anda untuk mengimplementasikannya sendiri :)

Sebagai latihan, Anda dapat mengerjakan soal:

1. SPOJ - ARRAYSUB
2. Codeforces 372C - Watching Fireworks is Fun
3. IOI 2006 - Pyramid. Tidak perlu khawatir dengan label IOI, ini soal lebih dari 10 tahun yang lalu