Range Minimum Query este o tehnică de programare dinamică care ne ajută să răspundem eficient la întrebări de forma „care este minimul dintre elementele v[x], v[x + 1], …, v[y]”, 1 <= x <= y <= n, atunci cand avem foarte multe interogări de acest tip. Evident, în loc de elementul minim, putem avea elementul maxim, dar acest lucru este ușor de modificat odată înțeles algoritmul.
Fie rmq[i][j] = minimul din secvența care se termină pe poziția j și are lungimea 2^i.
OBS: vom folosi linia 0 a matricei pentru elementele vectorului.
O secvență de lungime 2^i, cu capetele x și y, o putem împărți în al alte 2 secvențe de lungime 2^(i – 1). Prima secvență va ține de la x la x + 2^(i – 1) – 1, iar a doua de la y – 2^(i – 1) + 1 la y , așa că, minimul secvenței de lungime 2^i va fi elementul cel mai mic dintre minimele celor 2 secvențe care au lungimea 2^(i – 1). (1)
Așadar, (1) ne conduce la formula de recurență după care putem construi matricea rmq:
rmq[i][j] = min(rmq[i – 1][j – (1 << (i – 1))], rmq[i – 1][j]); (unde 1 << x înseamnă 2^x)
După construirea matricei, ne rămâne doar să răspundem la interogările de forma „care este minimul secvenței care ține de la indicele x și până la y”. Vom calcula eficient log2(y – x + 1) = l, iar răspunsul va fi min(rmq[l][x + (1 << l) – 1], rmq[l][y]) (2), adică minimul dintre elementul minim din secvența care începe pe poziția x și are lungimea 2^l și elementul minim al secvenței care se termină pe poziția y și are lungimea 2^l. Cele două secvențe arată astfel:
În cazul în care răspunsul se află în porțiunea comună celor două secvențe, înseamnă că rmq[l][x + (1 << l) – 1] și rmq[l][y] au aceeași valoare, prin urmare min(a, a) = a, deci rezultatul nu va fi afectat.
Exemplu implementare:
const int NMAX = 1e5;
int rmq[21][NMAX + 1], logaritm2[NMAX + 1], n, q, x, y;
int main(){
cin >> n >> q;
logaritm2[1] = 0;
for(int i = 1; i <= n; i++){
cin >> rmq[0][i];
if(i != 1)
logaritm2[i] = 1 + logaritm2[(i >> 1)];
}
for(int i = 1; i <= logaritm2[n]; i++)
for(int j = (1 << i); j <= n; j++)
rmq[i][j] = min(rmq[i - 1][j - (1 << (i - 1))], rmq[i - 1][j]);
int l = 0;
for(int i = 1; i <= q; i++){
cin >> x >> y;
l = logaritm2[y - x + 1];
cout << min(rmq[l][x + (1 << l) - 1], rmq[l][y]) << "\n";
}
}
Autor: Pirnog Theodor Ioan
Colegiul Național „B. P. Hasdeu”, Buzău