De ce contează?
Ai un șir lung de înălțimi care nu se schimbă niciodată și ești întrebat, din nou și din nou: „care e cea mai mică valoare între poziția 3 și poziția 17?”. Dacă de fiecare dată o iei la pas prin interval, pierzi timp degeaba. Mai deștept e să pregătești din timp niște „blocuri” gata-calculate, de lungimi 1, 2, 4, 8... (puteri ale lui 2). Atunci orice interval, oricât de lung, îl acoperi din DOUĂ astfel de blocuri și răspunzi instant.
Intuiția
Vrei minimul pe orice interval, instantaneu, dintr-un șir care NU se schimbă. Ideea e să plătești o singură dată, la început, un precalcul, ca apoi fiecare întrebare să coste aproape nimic: precalculezi minimul pe toate blocurile de lungime putere a lui 2.
Minimul nu se strică la SUPRAPUNERE: min(x, x) = x. De aceea orice interval
[l, r] se acoperă cu exact DOUĂ blocuri de aceeași lungime 2^k — unul lipit
de capătul stâng, unul de capătul drept — care se pot suprapune la mijloc fără
să altereze rezultatul. Două citiri din tabel, răspuns în O(1). Trucul merge
la orice operație idempotentă (min, max, gcd), dar NU la sumă, unde zona
suprapusă s-ar număra de două ori.