Sparse table
Në shqip: Tabela e rrallë
ShpjegimiSQ
Sparse table parallogarit minimumin për intervale me gjatësi 1, 2, 4, 8… dhe pastaj përgjigjet „cili është minimumi mes i dhe j?“ në O(1). E mirë kur vargu s'ndryshon.
EnglishEN
A sparse table precomputes minimums for ranges of length 1, 2, 4, 8… and then answers “what's the minimum between i and j?” in O(1). Good when the array doesn't change.
Si ta mendosh
Si një tabelë me përgjigje të gatshme për pyetjet e shpeshta.
Lexoje në anglisht
Like a table of ready answers to frequent questions.