De ce contează?
Ai un borcan plin cu monede și cineva te întreabă mereu „cât e suma?". Dacă le-ai număra monedă cu monedă de fiecare dată, ai pierde o veșnicie. În schimb, le grupezi în fișicuri de câte 10 și scrii pe fiecare fișic cât face. Acum, ca să afli totalul, aduni câteva fișicuri întregi (un număr scris, instant) și doar la capete numeri monedele rămase pe sfert. Exact asta face descompunerea în radical.
Intuiția
Spargi vectorul în blocuri de mărime aproximativ radical din n și, pentru fiecare bloc, ții pregătit un rezumat — aici, suma blocului. O întrebare despre un interval nu mai înseamnă „parcurge tot, element cu element": blocurile prinse complet în interval contribuie instant prin rezumatul lor, iar singurele elemente pe care chiar le atingi una câte una sunt cele de la cele două capete parțial acoperite.
Cheia este echilibrul: cu blocuri de mărime aproximativ radical din n ai cel mult ~radical din n blocuri întregi de adunat ȘI cel mult ~radical din n elemente la capete. Niciuna dintre cele două „cozi" de muncă nu o ia razna — de aceea o interogare costă O(radical din n), nu O(n).
Vezi cum funcționează
Folosește ← și → ca să pășești prin algoritm, sau Redă pentru animație. Urmărește cum interogarea „sare" peste blocurile întregi (citește un rezumat) și încetinește doar la capete, unde adună element cu element.
Pentru fiecare întrebare „suma pe [st, dr]?" parcurgi intervalul element cu element
și aduni: suma += v[i] pentru fiecare i de la st la dr. Simplu și corect.
O interogare costă până la n pași. La q = 100000 interogări pe un vector de
n = 100000 ajungi la q · n = 10 miliarde de operații — mult peste o secundă.
Sumele de prefix ar răspunde în O(1), dar dacă valorile se mai și modifică,
trebuie să reconstruiești prefixele în O(n) la fiecare actualizare. Niciuna nu e bună.
Împarte vectorul în blocuri de aproximativ radical din n elemente. Orice interval [st, dr] se acoperă cu cel mult două capete parțiale plus un șir de blocuri întregi la mijloc. Sunt cel mult ~radical din n blocuri întregi, fiecare citit în O(1) din rezumat, și cel mult ~radical din n elemente la capete. Total: O(radical din n).
Precalculezi sumaBloc[b] = suma elementelor din blocul b. La o interogare aduni
capetele parțiale element cu element și blocurile complet acoperite direct din
sumaBloc. La o actualizare punctuală modifici v[i] și ajustezi un singur
sumaBloc, în O(1).
Algoritmul pas cu pas
Fie vectorul de n = 9 elemente, cu blocuri de mărime 3 (radical din 9 = 3):
4 | 2 | 7 | 1 | 5 | 3 | 8 | 2 | 6 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Vrem suma pe intervalul [2, 7] (indicii 2,3,4,5,6,7). Privește unde cad capetele
față de granițele blocurilor:
4 | 2 | 7 | 1 | 5 | 3 | 8 | 2 | 6 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
st | dr |
Descompunem interogarea în trei zone:
- Capăt parțial stâng — blocul 0 nu e acoperit întreg, doar indicele
2:v[2] = 7. Îl adunăm element cu element. - Bloc întreg — blocul 1 (indicii 3,4,5) e complet în interval, deci luăm direct
rezumatul:
sumaBloc[1] = 9. Nu atingem cele 3 elemente individual. - Capăt parțial drept — blocul 2 e prins doar până la indicele
7, deci adunămv[6] + v[7] = 8 + 2 = 10.
Suma cerută = 7 + 9 + 10 = 26. Verificare directă: v[2]+v[3]+v[4]+v[5]+v[6]+v[7] = 7+1+5+3+8+2 = 26. ✓ Am atins doar 3 elemente la capete și am citit 1 rezumat,
în loc de a parcurge toate cele 6 poziții.
Implementare C++
#include <iostream>
#include <cmath>
using namespace std;
int v[100005];
long long sumaBloc[400]; // cel mult ~radical din n blocuri
int n, B; // B = marimea blocului
// precalcul: imparte in blocuri si insumeaza fiecare bloc
void build() {
B = (int)sqrt(n); // marime bloc aproximativ radical din n
if (B < 1) B = 1;
for (int i = 0; i < n; i++)
sumaBloc[i / B] += v[i]; // i / B = indicele blocului
}
// suma pe intervalul [st, dr], 0-indexat
long long query(int st, int dr) {
long long total = 0;
while (st <= dr && st % B != 0) // capat partial stang, element cu element
total += v[st++];
while (st + B - 1 <= dr) { // blocuri intregi, prin rezumat O(1)
total += sumaBloc[st / B];
st += B;
}
while (st <= dr) // capat partial drept, element cu element
total += v[st++];
return total;
}
// actualizare punctuala: v[i] devine v[i] + x, O(1)
void update(int i, int x) {
v[i] += x;
sumaBloc[i / B] += x; // ajustezi DOAR blocul care contine pozitia i
}
int main() {
n = 9;
int date[] = {4, 2, 7, 1, 5, 3, 8, 2, 6};
for (int i = 0; i < n; i++) v[i] = date[i];
build();
cout << query(2, 7) << "\n"; // 26
return 0;
}Bucla din mijloc avansează din bloc în bloc (st += B) și adună un rezumat o
singură dată per bloc — aici se ascunde câștigul. Capetele rămân scurte pentru că un
capăt parțial are mereu sub B elemente.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
Preprocesare (build) | O(n) | O(radical din n) |
O interogare (query) | O(radical din n) | O(1) |
O actualizare (update) | O(1) | O(1) |
La n = 100000, radical din n este în jur de 316. O interogare atinge sub ~600 de
poziții în loc de 100000 — de peste 150 de ori mai rapid, și suportă și actualizări,
spre deosebire de sumele de prefix.
Patru capcane frecvente:
- Mărimea blocului greșită. Dacă pui
B = 2sauB = n/2, costul nu mai e O(radical din n): cu blocuri mici ai prea multe blocuri întregi de parcurs, cu blocuri mari ai capete prea lungi. ȚineBîn jur de radical din n. - Granițele blocului off-by-one. Un bloc întreg poate fi adunat doar când
st + B - 1 <= dr(toate cele B poziții sunt în interval). Dacă scriist + B <= drsari un element; dacă uiți-1, incluzi un bloc care iese din interval. stșidrîn același bloc. Când intervalul cade tot într-un singur bloc, nu există niciun bloc întreg de adunat — trebuie să mergi element cu element pe toți. Aici contează gardast <= drdin bucla de capăt: fără ea ai dubla numărarea sau ai citi un rezumat care depășește intervalul. Verifică mereu codul pe un interval scurt, caquery(3, 4).- Uiți să actualizezi
sumaBloclaupdate. Dacă modificiv[i]dar nu ajustezi șisumaBloc[i / B], rezumatul rămâne învechit și interogările următoare care prind acel bloc întreg dau sume greșite.