Șmenul lui Batog (Square Root Decomposition)

Șmenul lui Batog (cunoscut și ca Square Root Decomposition sau descompunerea în radical) este o tehnică prin care împărțim un vector în blocuri de lungime √n și precalculăm informații pe fiecare bloc.

Astfel, putem răspunde la întrebări pe intervale în O(√n) în loc de O(n).

Problema

Avem un vector cu n elemente. Primim q operații de două tipuri:

1. Întrebare: care este suma/minimul/maximul pe intervalul [st, dr]?
2. Actualizare: modifică elementul de pe poziția poz la valoarea val.

Cu sume parțiale, răspundem la întrebări în O(1), dar actualizarea costă O(n) (trebuie recalculate).

Cu parcurgere, întrebarea costă O(n) iar actualizarea O(1).

Șmenul lui Batog oferă un compromis: ambele operații în O(√n).

Ideea

Împărțim vectorul în blocuri de lungime B ≈ √n.

Vector cu n = 16 elemente, B = 4:

Bloc 0:     Bloc 1:     Bloc 2:     Bloc 3:
[3 1 4 1]   [5 9 2 6]   [5 3 5 8]   [9 7 9 3]
 suma=9      suma=22     suma=21      suma=28

Pentru fiecare bloc, precalculăm suma (sau minimul, maximul - ce avem nevoie).

Cum răspundem la o întrebare?

Pentru intervalul [st, dr], avem 3 zone:

1. Coada din stânga: elementele de la st până la sfârșitul blocului - parcurgem individual
2. Blocuri complete: blocurile care se încadrează complet în interval - folosim sumele precalculate
3. Coada din dreapta: elementele de la începutul ultimului bloc până la dr - parcurgem individual

Interogare pe [2, 13]:

Bloc 0:     Bloc 1:     Bloc 2:     Bloc 3:
[3 1 4 1]   [5 9 2 6]   [5 3 5 8]   [9 7 9 3]
    ↑ ↑      complet      complet      ↑ ↑
  coada      bloc          bloc       coada
  stânga     complet      complet     dreapta

• Coada stânga: v[2] + v[3] = 4 + 1 = 5 (2 elemente)
• Blocuri complete: suma[1] + suma[2] = 22 + 21 = 43 (2 blocuri)
• Coada dreapta: v[12] + v[13] = 9 + 7 = 16 (2 elemente)
• Total: 5 + 43 + 16 = 64

Cel mult B elemente la coadă stânga + n/B blocuri + B elemente la coadă dreapta = O(√n).

Cum facem o actualizare?

Modificăm elementul v[poz] și recalculăm doar suma blocului care conține acea poziție.

v[5] = 100  (era 9)

Recalculăm doar suma blocului 1: 5 + 100 + 2 + 6 = 113
Celelalte blocuri rămân neschimbate.

Costul: O(B) = O(√n) - recalculăm un singur bloc.

Codul complet: sumă pe interval cu actualizări

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
long long bloc[320];   // √100000 ≈ 316
int n, q, B;

void construieste() {
    for (int i = 1; i <= n; i++)
        bloc[(i - 1) / B] = bloc[(i - 1) / B] + v[i];
}

void actualizeaza(int poz, int val) {
    int b = (poz - 1) / B;
    bloc[b] = bloc[b] - v[poz] + val;
    v[poz] = val;
}

long long suma(int st, int dr) {
    long long s = 0;
    int bSt = (st - 1) / B;
    int bDr = (dr - 1) / B;

    if (bSt == bDr) {
        // st și dr sunt în același bloc
        for (int i = st; i <= dr; i++)
            s = s + v[i];
        return s;
    }

    // Coada stânga: de la st până la sfârșitul blocului bSt
    for (int i = st; (i - 1) / B == bSt; i++)
        s = s + v[i];

    // Blocuri complete
    for (int b = bSt + 1; b < bDr; b++)
        s = s + bloc[b];

    // Coada dreapta: de la începutul blocului bDr până la dr
    for (int i = bDr * B + 1; i <= dr; i++)
        s = s + v[i];

    return s;
}

int main()
{
    fin >> n >> q;
    B = 1;
    while ((B + 1) * (B + 1) <= n) B++;

    for (int i = 1; i <= n; i++)
        fin >> v[i];

    construieste();

    for (int i = 1; i <= q; i++) {
        int tip;
        fin >> tip;
        if (tip == 1) {
            int st, dr;
            fin >> st >> dr;
            fout << suma(st, dr) << "\n";
        } else {
            int poz, val;
            fin >> poz >> val;
            actualizeaza(poz, val);
        }
    }

    return 0;
}

date.in:

8 4
3 1 4 1 5 9 2 6
1 1 8
1 3 6
2 5 100
1 1 8

date.out:

31
19
126

Explicație

• 1 1 8 - suma pe [1, 8] = 3+1+4+1+5+9+2+6 = 31
• 1 3 6 - suma pe [3, 6] = 4+1+5+9 = 19
• 2 5 100 - v[5] devine 100 (era 5)
• 1 1 8 - suma pe [1, 8] = 3+1+4+1+100+9+2+6 = 126

Pas cu pas: funcția suma(3, 14) pe un vector cu n=16, B=4

Indici:  1  2  3  4 | 5  6  7  8 | 9  10 11 12 | 13 14 15 16
Blocuri:  bloc 0    |  bloc 1    |  bloc 2     |  bloc 3

• bSt = (3-1)/4 = 0, bDr = (14-1)/4 = 3
• Coada stânga: v[3] + v[4] (restul blocului 0)
• Blocuri complete: bloc[1] + bloc[2]
• Coada dreapta: v[13] + v[14] (începutul blocului 3)

Total: 4 operații pe elemente + 2 operații pe blocuri = 6 operații (în loc de 12 cu parcurgere).

Calculul lui B

Alegem B = √n pentru a echilibra costurile:

• Coada stânga: cel mult B elemente
• Coada dreapta: cel mult B elemente
• Blocuri complete: cel mult n / B blocuri
• Total: B + n/B

Minimul expresiei B + n/B se atinge când B = √n.

Varianta cu minim pe interval

Aceeași idee, dar în loc de sumă, păstrăm minimul fiecărui bloc:

int bloc[320]; // minimul pe fiecare bloc

void construieste() {
    for (int b = 0; b * B < n; b++) {
        bloc[b] = v[b * B + 1];
        for (int i = b * B + 2; i <= min(n, (b + 1) * B); i++)
            if (v[i] < bloc[b])
                bloc[b] = v[i];
    }
}

int minim(int st, int dr) {
    int mn = v[st];
    int bSt = (st - 1) / B;
    int bDr = (dr - 1) / B;

    if (bSt == bDr) {
        for (int i = st; i <= dr; i++)
            if (v[i] < mn) mn = v[i];
        return mn;
    }

    for (int i = st; (i - 1) / B == bSt; i++)
        if (v[i] < mn) mn = v[i];

    for (int b = bSt + 1; b < bDr; b++)
        if (bloc[b] < mn) mn = bloc[b];

    for (int i = bDr * B + 1; i <= dr; i++)
        if (v[i] < mn) mn = v[i];

    return mn;
}

Comparație cu alte tehnici

Sqrt decomposition nu e cea mai rapidă, dar este simplu de implementat și suficient de eficientă pentru majoritatea problemelor.

Greșeli frecvente

1. Indicii blocurilor calculați greșit

Cu indexare de la 1: blocul elementului i este (i - 1) / B. Cu indexare de la 0: blocul elementului i este i / B.

Atenție la consistență.

2. Cazul bSt == bDr (același bloc)

Când st și dr sunt în același bloc, nu avem blocuri complete - parcurgem doar elementele. Dacă uiți acest caz, calculul e greșit.

3. B calculat greșit

B = 1;
while ((B + 1) * (B + 1) <= n) B++;

Sau mai simplu:

#include <cmath>
B = (int)sqrt(n);
if (B < 1) B = 1;

4. Vectorul de blocuri prea mic

Dacă n = 100.000 și B = 316, avem 100.000 / 316 + 1 ≈ 317 blocuri. Declară vectorul de blocuri cu cel puțin 320 elemente.

Ce să reții

• Sqrt decomposition împarte vectorul în blocuri de √n elemente.
• Precalculăm informația (sumă, minim, maxim) pe fiecare bloc.
• Întrebarea: parcurgem cozile + sumăm blocuri complete = O(√n).
• Actualizarea: modificăm elementul + recalculăm un bloc = O(√n).
• Cazul special: dacă st și dr sunt în același bloc, parcurgem direct.
• Este un compromis între simplitate și eficiență.
• Ideală când avem amestec de actualizări și interogări.