De ce contează?
Imaginează-ți un raft foarte lung cu mii de cărți. Cineva te întreabă mereu: „câte pagini sunt, în total, între cartea 200 și cartea 700?" Dacă numeri pagină cu pagină de fiecare dată, te epuizezi. Așa că împarți raftul în cutii egale și scrii pe fiecare cutie totalul ei. Acum, ca să răspunzi, aduni doar cutiile întregi care încap între cele două capete, plus câteva cărți răzlețe de la margini. Atingi câteva cutii, nu mii de cărți. Asta e square root decomposition.
Intuiția
Ai un șir de n numere și primești multe interogări de forma „care e suma pe
intervalul de la l la r?", amestecate cu actualizări „schimbă v[poz]".
Ideea-cheie: grupezi elementele în blocuri de mărime aproximativ radical din
n și ții pentru fiecare bloc suma lui precalculată. Un interval lung
acoperă câteva blocuri întregi (le iei suma dintr-o dată) plus două capete care
ies parțial din blocurile lor (pe astea le numeri element cu element). Nici prea
multe blocuri, nici prea multe elemente răzlețe — exact echilibrul.
Orice interval [l, r] se descompune în câteva blocuri întregi (cu sumele
gata calculate) plus cel mult două capete parțiale. Cu blocuri de mărime k
plătești cel mult n/k blocuri întregi și cel mult 2k elemente răzlețe, iar
suma n/k + 2k e cea mai mică atunci când k e aproximativ radical din n.
De aici „radicalul" din nume: e exact punctul de echilibru.