De ce contează?
Ai învățat deja câteva unelte care răspund repede la întrebări: sume parțiale, heap, arbore binar de căutare, Fenwick, Segment Tree, Union-Find. E o trusă de scule: ciocan, șurubelniță, cheie. Nimeni nu te întreabă „care e cea mai bună sculă?" — întrebarea corectă e „ce am de făcut des?". Bați cuie? Iei ciocanul. La fel aici: nu memorezi care structură e „cea mai tare", ci te uiți la CE întrebări pune problema cel mai des și alegi unealta care răspunde la ele în timp logaritmic.
Ideea-cheie
Toate aceste structuri fac același lucru abstract: țin o colecție de valori și răspund rapid la interogări și actualizări. Diferența dintre ele nu e „cât de avansate sunt", ci ce tip de operație fac ieftină. Un heap îți dă minimul instant, dar nu știe să caute un element oarecare. Un Fenwick îți dă suma unui prefix instant, dar nu știe să-ți spună minimul global la fel de simplu.
Decizia are două trepte. Prima întrebare: datele se schimbă? Dacă șirul e
citit o dată și rămâne fix, iar apoi curg doar întrebări, nu-ți trebuie nicio
structură „vie": precalculezi — de pildă sume parțiale — și răspunzi la
fiecare interogare în O(1). Abia dacă update-urile se intercalează cu
interogările intri în lumea structurilor dinamice. A doua întrebare: ce
operație domină? Te uiți la enunț și numeri ce întrebări apar cel mai des și
pe ce date. Dacă problema cere de mii de ori „dă-mi minimul curent și
scoate-l", structura se alege singură: heap. Dacă cere de mii de ori „suma
valorilor de la poziția 1 la poziția k", cu modificări între întrebări, se
alege Fenwick.
Întrebarea din enunț îți dictează structura. Prima treaptă: static sau dinamic? — fără update-uri, precalculul (sume parțiale) bate orice structură. A doua treaptă: ce operație domină? — sumă de prefix, minim pe interval, extrem global, căutare ordonată. Restul deciziei decurge din aceste două răspunsuri, nu din lista structurilor pe care le știi.