{"id":370,"date":"2022-05-03T22:14:46","date_gmt":"2022-05-03T22:14:46","guid":{"rendered":"https:\/\/solinfo.ro\/blog\/?p=370"},"modified":"2024-05-17T20:31:18","modified_gmt":"2024-05-17T20:31:18","slug":"programare-dinamica-range-minimum-query","status":"publish","type":"post","link":"https:\/\/solinfo.ro\/blog\/programare-dinamica-range-minimum-query\/","title":{"rendered":"Programare dinamic\u0103 – Range Minimum Query"},"content":{"rendered":"\n

Range Minimum Query este o tehnic\u0103 de programare dinamic\u0103 care ne ajut\u0103 s\u0103 r\u0103spundem eficient la \u00eentreb\u0103ri de forma „care este minimul dintre elementele v[x], v[x + 1], …, v[y]”, 1 <= x <= y <= n, atunci cand avem foarte multe interog\u0103ri de acest tip. Evident, \u00een loc de elementul minim, putem avea elementul maxim, dar acest lucru este u\u0219or de modificat odat\u0103 \u00een\u021beles algoritmul.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Fie rmq[i][j] = minimul din secven\u021ba care se termin\u0103 pe pozi\u021bia j \u0219i are lungimea 2^i. <\/p>\n\n\n\n

OBS: vom folosi linia 0 a matricei pentru elementele vectorului.<\/p>\n\n\n\n

O secven\u021b\u0103 de lungime 2^i, cu capetele x <\/strong>\u0219i y<\/strong>, o putem \u00eemp\u0103r\u021bi \u00een al alte 2 secven\u021be de lungime 2^(i – 1). Prima secven\u021b\u0103 va \u021bine de la x<\/strong> la x + 2^(i – 1) – 1<\/strong>, iar a doua de la y – 2^(i – 1) + 1 <\/strong>la y<\/strong> , a\u0219a c\u0103, minimul secven\u021bei de lungime 2^i va fi elementul cel mai mic dintre minimele celor 2 secven\u021be care au lungimea 2^(i – 1). (1)<\/p>\n\n\n\n

A\u0219adar, (1) ne conduce la formula de recuren\u021b\u0103 dup\u0103 care putem construi matricea rmq<\/strong><\/em>:<\/p>\n\n\n\n

rmq[i][j] = min(rmq[i – 1][j – (1 << (i – 1))], rmq[i – 1][j]);<\/em> (unde 1 << x \u00eenseamn\u0103 2^x)<\/p>\n\n\n\n

\n
\"\"<\/figure>\n<\/figure>\n\n\n\n

Dup\u0103 construirea matricei, ne r\u0103m\u00e2ne doar s\u0103 r\u0103spundem la interog\u0103rile de forma „care este minimul secven\u021bei care \u021bine de la indicele x \u0219i p\u00e2n\u0103 la y”. Vom calcula eficient log2(y – x + 1) = l, iar r\u0103spunsul va fi min(rmq[l][x + (1 << l) – 1], rmq[l][y])<\/em> (2), adic\u0103 minimul dintre elementul minim din secven\u021ba care \u00eencepe pe pozi\u021bia x <\/strong>\u0219i are lungimea 2^l<\/strong> \u0219i elementul minim al secven\u021bei care se termin\u0103 pe pozi\u021bia y<\/strong> \u0219i are lungimea 2^l<\/strong>. Cele dou\u0103 secven\u021be arat\u0103 astfel:<\/p>\n\n\n\n

\n
\"\"<\/figure>\n<\/figure>\n\n\n\n

\u00cen cazul \u00een care r\u0103spunsul se afl\u0103 \u00een por\u021biunea comun\u0103 celor dou\u0103 secven\u021be, \u00eenseamn\u0103 c\u0103 rmq[l][x + (1 << l) – 1] \u0219i rmq[l][y] au aceea\u0219i valoare, prin urmare min(a, a) = a, deci rezultatul nu va fi afectat.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Exemplu implementare:<\/p>\n\n\n\n

const int NMAX = 1e5;\nint rmq[21][NMAX + 1], logaritm2[NMAX + 1], n, q, x, y;\n \nint main(){\n \n    cin >> n >> q;\n    logaritm2[1] = 0;\n \n    for(int i = 1; i <= n; i++){\n \n        cin >> rmq[0][i];\n \n        if(i != 1)\n            logaritm2[i] = 1 + logaritm2[(i >> 1)];\n \n    }\n \n    for(int i = 1; i <= logaritm2[n]; i++)\n        for(int j = (1 << i); j <= n; j++)\n            rmq[i][j] = min(rmq[i - 1][j - (1 << (i - 1))], rmq[i - 1][j]);\n \n    int l = 0;\n    for(int i = 1; i <= q; i++){\n \n        cin >> x >> y;\n        l = logaritm2[y - x + 1];\n \n        cout << min(rmq[l][x + (1 << l) - 1], rmq[l][y]) << \"\\n\";\n \n    }\n \n \n}\n\n<\/pre>\n\n\n\n
Autor: Pirnog Theodor Ioan<\/p>\n\n\n\n
Colegiul Na\u021bional „B. P. Hasdeu”, Buz\u0103u<\/p>\n","protected":false},"excerpt":{"rendered":"
Range Minimum Query este o tehnic\u0103 de programare dinamic\u0103 care ne ajut\u0103 s\u0103 r\u0103spundem eficient la \u00eentreb\u0103ri de forma „care … <\/p>\n","protected":false},"author":3,"featured_media":377,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-370","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/370","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/comments?post=370"}],"version-history":[{"count":6,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/370\/revisions"}],"predecessor-version":[{"id":523,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/370\/revisions\/523"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/377"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=370"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=370"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=370"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}