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 :)
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.
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).
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).
