Sparse Table

Sparse Table este o structură de date care răspunde la interogări de tip minim sau maxim pe un interval [st, dr] în O(1), după o precalculare de O(n log n).

Este ideală pentru probleme fără actualizări (vectorul nu se modifică) - cunoscută ca problema RMQ (Range Minimum/Maximum Query).

Problema

Avem un vector cu n elemente și q întrebări:

Care este minimul/maximul pe intervalul [st, dr]?

Sparse Table are cea mai rapidă interogare posibilă.

Ideea

Precalculăm răspunsul pentru toate intervalele cu lungime putere de 2: lungime 1, 2, 4, 8, 16, …

Definim sp[k][i] = minimul pe intervalul de lungime 2^k care începe la poziția i.

• sp[0][i] = v[i] (interval de lungime 1)
• sp[1][i] = min(v[i], v[i+1]) (interval de lungime 2)
• sp[2][i] = min(v[i], v[i+1], v[i+2], v[i+3]) (interval de lungime 4)
• …

Exemplu

v:  3  1  4  1  5  9  2  6

sp[0]: 3  1  4  1  5  9  2  6    (lungime 1)
sp[1]: 1  1  1  1  5  2  2  -    (lungime 2)
sp[2]: 1  1  1  1  2  2  -  -    (lungime 4)
sp[3]: 1  1  -  -  -  -  -  -    (lungime 8)

sp[2][3] = min(v[3], v[4], v[5], v[6]) = min(4, 1, 5, 9) = 1

Construirea

Formula de recurență:

sp[k][i] = min(sp[k-1][i], sp[k-1][i + 2^(k-1)])

Împărțim intervalul de lungime 2^k în două jumătăți de lungime 2^(k-1):

Interval [i, i + 2^k - 1]:

[──── sp[k-1][i] ────][──── sp[k-1][i + 2^(k-1)] ────]
         2^(k-1)                    2^(k-1)

// sp[0][i] = v[i]
for (int i = 1; i <= n; i++)
    sp[0][i] = v[i];

// Construim pentru k = 1, 2, ...
for (int k = 1; (1 << k) <= n; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++)
        sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);

Interogarea în O(1)

Pentru intervalul [st, dr]:

1. Calculăm k = cel mai mare exponent astfel încât 2^k <= dr - st + 1 (lungimea intervalului).
2. Răspunsul = min(sp[k][st], sp[k][dr - 2^k + 1]).

Cele două intervale de lungime 2^k se suprapun, dar asta nu e o problemă pentru min/max (minimul nu se schimbă dacă verificăm un element de două ori).

Interogare [st, dr]:

[──── sp[k][st] ────────]
        [──── sp[k][dr - 2^k + 1] ────]

Se suprapun la mijloc - OK pentru min/max!

Precalcularea lui k

int lg[100001];
lg[1] = 0;
for (int i = 2; i <= n; i++)
    lg[i] = lg[i / 2] + 1;

lg[x] = floor(log2(x)).

Interogarea

int query(int st, int dr) {
    int k = lg[dr - st + 1];
    return min(sp[k][st], sp[k][dr - (1 << k) + 1]);
}

Codul complet: RMQ (Range Minimum Query)

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

int v[100001];
int sp[17][100001];  // log2(100000) ≈ 16
int lg[100001];
int n, q;

void construieste() {
    for (int i = 1; i <= n; i++)
        sp[0][i] = v[i];

    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);

    lg[1] = 0;
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
}

int query(int st, int dr) {
    int k = lg[dr - st + 1];
    return min(sp[k][st], sp[k][dr - (1 << k) + 1]);
}

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

    construieste();

    for (int i = 1; i <= q; i++) {
        int st, dr;
        fin >> st >> dr;
        fout << query(st, dr) << "\n";
    }

    return 0;
}

date.in:

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

date.out:

1
1
2
1

Verificare

• [1,8]: min(3,1,4,1,5,9,2,6) = 1
• [3,6]: min(4,1,5,9) = 1
• [5,8]: min(5,9,2,6) = 2
• [2,4]: min(1,4,1) = 1

Pas cu pas: query(3, 6)

Lungime interval = 6 - 3 + 1 = 4
k = lg[4] = 2
2^k = 4

sp[2][3] = min(v[3], v[4], v[5], v[6]) = min(4, 1, 5, 9) = 1
sp[2][3] = sp[2][6 - 4 + 1] = sp[2][3]   (se suprapun complet)

Răspuns: min(1, 1) = 1 ✓

Alt exemplu: query(2, 7):

Lungime = 6, k = lg[6] = 2, 2^k = 4

sp[2][2] = min(v[2], v[3], v[4], v[5]) = min(1, 4, 1, 5) = 1
sp[2][4] = min(v[4], v[5], v[6], v[7]) = min(1, 5, 9, 2) = 1

Răspuns: min(1, 1) = 1

Suprapunere: [2,5] și [4,7] se suprapun pe [4,5] - OK!

Varianta cu maxim

Schimbăm doar min cu max:

void construieste() {
    for (int i = 1; i <= n; i++)
        sp[0][i] = v[i];

    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
}

int query(int st, int dr) {
    int k = lg[dr - st + 1];
    return max(sp[k][st], sp[k][dr - (1 << k) + 1]);
}

De ce NU funcționează pentru sumă?

La min/max, suprapunerea nu contează - minimul rămâne același chiar dacă verificăm un element de două ori.

La sumă, suprapunerea adaugă elementele din zona comună de două ori - rezultatul e greșit.

Pentru sumă pe interval, folosim sume parțiale (O(1)) sau Segment Tree (O(log n) cu actualizări).

Memorie

sp are log2(n) + 1 linii și n coloane.

Pentru n = 100.000, declarăm sp[17][100001] - aproximativ 6.5 MB.

Comparație completă

Sparse Table e cea mai rapidă la interogare dar nu suportă actualizări.

Greșeli frecvente

1. Dimensiunea lui sp greșită

int sp[20][100001]; // 2^20 > 100000, deci 20 e suficient

Dacă n poate fi 100.000, avem nevoie de maxim log2(100000) ≈ 17 niveluri. Declaram sp[18][...] ca să fim siguri.

2. Formula de query greșită

// GREȘIT:
sp[k][dr - (1 << k)]     // lipsește +1

// CORECT:
sp[k][dr - (1 << k) + 1]

3. Folosirea pentru sumă

Sparse Table cu suprapunere funcționează doar pentru min, max, gcd - operații idempotente (aplicarea de două ori pe același element nu schimbă rezultatul).

4. Uitarea precalculării lui lg

// Fără lg precalculat, trebuie calculat la fiecare query
// Cu lg precalculat - O(1) per query

Ce să reții

• Sparse Table precalculează min/max pe intervale de lungime putere de 2.
• Construire: sp[k][i] = min(sp[k-1][i], sp[k-1][i + 2^(k-1)]) - O(n log n).
• Interogare: min(sp[k][st], sp[k][dr - 2^k + 1]) - O(1).
• Funcționează doar pentru min, max, gcd (operații idempotente).
• Nu suportă actualizări.
• Precalculăm lg[i] = floor(log2(i)) pentru interogări rapide.
• 1 << k = 2^k (shift pe biți).