De ce contează?
Un mecanic bun nu folosește aceeași cheie la orice șurub — alege unealta după problemă. Ai învățat un set de tehnici pe vectori: frecvențe, sume parțiale, fereastră, two pointers, difference array, căutare binară, Kadane. Lecția asta te învață când alegi pe care.
Întreabă-te: ce cere problema?
Nu tehnica e punctul de plecare, ci forma întrebării. Recunoaște tiparul, apoi alege unealta:
| Întrebarea sună a... | Tehnica potrivită | Cost |
|---|---|---|
| „de câte ori apare valoarea x?" | vector de frecvență | O(n) constr., O(1) interog. |
| „suma pe intervalul [st, dr]?" (vector fix) | sume parțiale | O(n) + O(1)/interog. |
| „adună x pe [st, dr]" de multe ori | difference array | O(n + q) |
| „cea mai bună secvență de lungime k" | fereastră glisantă | O(n) |
| „pereche/secvență cu o proprietate" (sortat) | two pointers | O(n) |
| „există valoarea x?" (sortat) | căutare binară | O(log n) |
| „subsecvența de sumă maximă" | Kadane | O(n) |
| „sortează valori mici dintr-un interval" | sortare prin numărare | O(n + V) |
Două cuvinte-cheie te ghidează: „interval" trimite spre sume parțiale / difference array / fereastră; „sortat" trimite spre căutare binară / two pointers. Identifică-le în enunț înainte să scrii cod.
Interogare vs actualizare — distincția centrală
- Doar citești sume pe interval, vectorul nu se schimbă → sume parțiale.
- Modifici intervale, citești la final → difference array.
Sunt operații inverse (una desface ce face cealaltă). Confuzia lor e o greșeală frecventă.
Fix vs glisant — a doua distincție
- Întrebare despre un interval dat [st, dr] → sume parțiale (sari direct).
- Întrebare despre toate secvențele de o lungime → fereastră glisantă (aluneci incremental).
Limita lui n confirmă alegerea
Chiar dacă ai tehnica, verifică n din enunț (vezi [[punte-complexitate]]):
n ≤ 5000→ O(n²) naiv poate trece, nu te complica.n ~ 10⁶→ ai nevoie de O(n) sau O(n log n): exact tehnicile de mai sus.
Capcane reale la alegerea tehnicii:
- Sume parțiale când intervalele se modifică: dacă vectorul se schimbă între interogări, sumele parțiale precalculate devin invalide. Acolo e nevoie de difference array sau structuri mai avansate.
- Two pointers / căutare binară pe vector nesortat: ambele presupun sortare. Pe date nesortate dau rezultate greșite — sortează întâi.
- Fereastră glisantă recalculată de la zero: pierzi avantajul O(n); actualizează incremental.
- Forțezi o tehnică „la modă": alegi Kadane sau two pointers unde o simplă parcurgere O(n) ajungea. Cea mai simplă soluție corectă care intră în timp e cea bună.
De reținut
- Pornești de la forma întrebării, nu de la tehnică: „interval" și „sortat" sunt cuvintele-cheie.
- Interogare pe interval fix → sume parțiale; actualizare pe interval → difference array.
- Confirmă cu limita lui
n; alege cea mai simplă tehnică corectă care intră în timp.