Feladatok‎ > ‎

A részsorozat legkisebb eleme (Range Minimum Query)

Adott egy N hosszú számsorozat (a0, a1, … an-1). A feladat, hogy írj programot, ami minél jobb időben kiszámolja tetszőleges i, j-re (0≤i≤j<n) ai, ai+1, … aj részsorozat minimumát.

Az optimalizált RMQ algoritmusok első lépésben előkészítenek egy speciális adatszerkezetet a számsorozat alapján, majd ennek felhasználásával gyorsabban meg tudják válaszolni a minimum lekérdéseket. Az algoritmusokat általában az adatszerkezet mérete és a lekérdezés ideje alapján hasonlítják össze.

Bővebben: https://en.wikipedia.org/wiki/Range_minimum_query

n log n memória, konstans idő

Az adatszerkezetben eltároljuk, hogy a 20, 21, 22, 23, … hosszú, l-edik elemtől kezdődő részsorozat minimuma mennyi.

Kiolvasásnál kettő ilyen adatot olvasunk ki az adatszerkezetből, kiszámoljuk a legnagyobb 2-hatványt, ami még nem nagyobb i és j különbségénél. Az ilyen részsorozatok közül kiválasztjuk azt, amelyik i-vel kezdődik, és amelyik j-vel végződik. A két részsorozat biztosan átfedi egymást, ezért ha mindkettő részsorozatra lekérjük a minimumot, majd a kapott két minimum minimumát vesszük, megkapjuk az eredményt.