De ce contează?
Imaginează-ți un clasament viu de joc online: mii de jucători, scoruri care se schimbă în fiecare secundă. La orice moment vrei să răspunzi instant „care e suma punctelor primilor k jucători?". Dacă de fiecare dată când un singur scor crește ai reface tot clasamentul, ai rămâne mereu în urmă. Ai nevoie de o structură care și se actualizează repede, și răspunde repede.
Intuiția
Până acum, la lecția de interogări, ai văzut că poți răspunde la „suma pe un
interval" foarte rapid dacă șirul stă pe loc. Realitatea însă e dinamică:
elementele se schimbă. Întrebarea acestei lecții e despre dualitate — ai
nevoie, în același timp, de două operații pe același șir: să modifici un element
(update) și să afli o sumă (query). Vrei ca amândouă să fie ieftine. O
structură care e tare doar la una și catastrofală la cealaltă nu te ajută.
Ideea centrală a lecției: o schimbare la poziția i nu trebuie să atingă toate
precalculările — dacă ții sume pe bucăți ierarhice, poziția i aparține doar
la O(log n) dintre ele. Repari doar acele bucăți, iar interogarea rămâne tot o
sumă de puține bucăți. Așa devin ambele operații rapide.