Square Root Decomposition

De ce contează?

Ai o bibliotecă uriașă și te întreabă cineva „câte cărți sunt pe rafturile 30 până la 95?”. Dacă numeri carte cu carte, dureazi o veșnicie. Mai bine ții pe fiecare raft un bilețel cu totalul lui: aduni bilețelele rafturilor pline și numeri la mână doar capetele. Asta e square root decomposition.

Ce este square root decomposition

E o tehnică prin care împărți un vector de n elemente în blocuri de mărime ≈ √n și precalculezi un agregat pentru fiecare bloc (suma, minimul, maximul…). Apoi o interogare pe un interval se rezolvă combinând:

blocurile complet conținute → folosești valoarea precalculată (rapid);
capetele parțiale → parcurgi element cu element (puține elemente).

Observația-cheie

Magia stă în echilibru: sunt cel mult ~√n blocuri întregi și cel mult ~√n elemente la capete. Orice interogare costă O(√n), mult mai bine decât O(n) per interogare când ai multe interogări.

Algoritmul pas cu pas

Vector de n = 9 elemente, blocuri de mărime 3:

a	2	5	1	3	8	2	7	4	6
	0	1	2	3	4	5	6	7	8

Vector de 9 elemente, împărțit mental în 3 blocuri de câte 3: [2 5 1] [3 8 2] [7 4 6].

Sumele pe blocuri (precalculate o singură dată):

bloc	8	13	17
bloc	0	1	2

Suma fiecărui bloc: blocul 0 = 8, blocul 1 = 13, blocul 2 = 17.

Interogare: suma pe [2, 7] (indici 0-based):

Capăt parțial stâng: indicele 2 (1) — în blocul 0, dar blocul nu e complet acoperit → adun direct: 1.
Blocul 1 (indici 3–5) e complet în interval → iau suma precalculată: 13.
Capăt parțial drept: indicii 6, 7 (7, 4) — în blocul 2, neacoperit complet → adun direct: 11.
Total: 1 + 13 + 11 = 25.

Implementare C++

#include <iostream>
#include <cmath>
using namespace std;

const int N = 100005;
long long a[N], bloc[400];   // bloc[k] = suma blocului k
int n, len;                  // len = marimea blocului ~ sqrt(n)

void build() {
    len = (int)sqrt(n) + 1;
    for (int i = 0; i < n; i++)
        bloc[i / len] += a[i];     // fiecare element contribuie la blocul lui
}

long long query(int st, int dr) {  // suma pe [st, dr], 0-based
    long long s = 0;
    while (st <= dr && st % len != 0) s += a[st++];      // capat partial stang
    while (st + len - 1 <= dr) { s += bloc[st / len]; st += len; }  // blocuri intregi
    while (st <= dr) s += a[st++];                        // capat partial drept
    return s;
}

void update(int i, long long val) {  // a[i] = val
    bloc[i / len] += val - a[i];      // ajustezi doar blocul lui
    a[i] = val;
}

int main() {
    n = 9;
    long long t[9] = {2,5,1,3,8,2,7,4,6};
    for (int i = 0; i < n; i++) a[i] = t[i];
    build();
    cout << query(2, 7) << "\n";   // 25
    update(4, 0);                  // a[4]: 8 -> 0
    cout << query(2, 7) << "\n";   // 17
    return 0;
}

Complexitate

Operație	Timp	Spațiu
Construcție	O(n)	O(n + √n)
Interogare pe interval	O(√n)	—
Actualizare element	O(1)	—

Greșeli frecvente

Capcane reale de concurs:

Off-by-one la capete. Condițiile st % len != 0 și st + len - 1 <= dr sunt delicate. Testează pe un interval mic, la mână, înainte de submisie.
Overflow. Sumele pe blocuri cresc repede. Folosește long long pentru a și bloc.
Uiți să ajustezi blocul la update. Schimbi a[i] dar nu și bloc[i/len] → toate interogările următoare sunt greșite.
Bloc prea mare sau prea mic. Cu len = n ai O(n) per interogare; cu len = 1 ai O(n) pe blocuri. Ține-l aproape de √n.

Vizualizare

Urmărește cum o interogare folosește blocurile întregi precalculate și parcurge doar capetele parțiale element cu element:

Indiciu

Folosește ← și → pentru a avansa pas cu pas, sau apasă Redă pentru animație automată.

Recapitulare

Împarți vectorul în blocuri de ≈ √n și precalculezi un agregat per bloc.
Interogarea combină blocurile întregi (precalculate) cu capetele parțiale (directe) → O(√n).
Actualizarea unui element ajustează doar blocul lui; atenție la off-by-one și overflow.