De ce contează?
Ai un tablou de scor care se schimbă mereu și cineva te tot întreabă: „care e suma punctelor între rândul 4 și rândul 9?”, apoi „dar acum, între 2 și 7?”. Dacă de fiecare dată aduni la mână toate rândurile din interval, pierzi timp pe aceleași numere. Ar fi mult mai bine să ai răspunsuri gata-calculate pe bucăți, din care să asamblezi rapid orice interval cerut. Asta e ideea interogărilor pe intervale.
Intuiția
O interogare pe interval cere o singură valoare care rezumă o porțiune
[st, dr] din șir: suma, minimul, maximul, etc. Naiv, parcurgi intervalul și
combini element cu element. Dacă ai multe interogări, repeți munca pe aceleași
zone iar și iar. Declicul: precalculezi răspunsuri pe intervale-bloc,
organizate ca un arbore peste șir — fiecare nod ține răspunsul unui interval,
iar orice [st, dr] se compune din câteva astfel de blocuri, nu din toate
elementele.
Ideea centrală: orice interval [st, dr] se acoperă cu cel mult două blocuri
pe fiecare nivel al arborelui (câte unul lângă fiecare margine), iar arborele
are O(log n) niveluri. Deci orice interogare — oricât de lung ar fi intervalul —
se asamblează din O(log n) răspunsuri gata-calculate.