{"id":458,"date":"2022-12-07T07:33:29","date_gmt":"2022-12-07T07:33:29","guid":{"rendered":"https:\/\/solinfo.ro\/blog\/?p=458"},"modified":"2024-05-17T20:31:18","modified_gmt":"2024-05-17T20:31:18","slug":"structuri-de-date-arborescente-arbori-de-intervale","status":"publish","type":"post","link":"https:\/\/solinfo.ro\/blog\/structuri-de-date-arborescente-arbori-de-intervale\/","title":{"rendered":"Structuri de date arborescente – Arbori de intervale"},"content":{"rendered":"\n

Un arbore de intervale este o structur\u0103 de date similar\u0103 cu un arbore binar, \u00een care fiecare nod con\u0163ine informa\u0163ii despre un anumit interval dintr-un \u015fir. La cazul general, un nod re\u021bine informa\u021bii despre intervalul [st, dr]. Dac\u0103 intervalul asociat nodului are lungimea mai mare dec\u00e2t 1, nodului curent \u00eei vor fi asociate alte dou\u0103 noduri ce vor descrie intervalele [st, mid] \u0219i [mid + 1, dr], unde mid = (st + dr) \/ 2. <\/p>\n\n\n\n

Pentru a \u00een\u021belege mai bine cum arat\u0103 un astfel de arbore, vom considera \u0219irul cu 7 elemente v<\/strong> = (4, 3, -1, 2, 9, 10, 6). Vrem s\u0103 afl\u0103m suma elementelor dintr-un anumit interval de pozi\u021bii din \u0219irul v<\/strong>. Arborele de intervale asociat lui v<\/strong> va fi:<\/p>\n\n\n\n

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

Vom construi arborele recursiv, folosind un vector. Dimensiunea vectorului va fi 4 * N<\/strong>, deoarece num\u0103rul de noduri este egal cu: 1 + 2 + 4 + … + 2^[log2(N)] < 2^([log2(N)] + 1) < 4 * N<\/strong>.<\/em> Ulterior, vom vedea \u0219i ce opera\u021bii putem face cu acest arbore.<\/p>\n\n\n\n

Pentru a identifica nodurile, fiii nodului cu num\u0103rul k<\/strong> vor fi nodurile cu numerele 2 * k (pentru nodul din st\u00e2nga), respectiv 2 * k + 1 (pentru nodul din dreapta).<\/strong> R\u0103d\u0103cina o vom numerota cu 1<\/strong>.<\/p>\n\n\n\n

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

    \n
  • Construirea arborelui de intervale \u00een O(N)<\/strong><\/li>\n<\/ul>\n\n\n\n

    Vom construi arborele recursiv, folosind urm\u0103toarele observa\u021bii:<\/p>\n\n\n\n

    a) dac\u0103 nodul curent descrie un interval cu un singur element, atunci el va lua valoarea din \u0219ir asociat\u0103 pozi\u021biei corespunz\u0103toare;<\/p>\n\n\n\n

    b) dac\u0103 nodul curent descrie un interval cu mai multe elemente, atunci el va fi suma valorilor fiilor.<\/p>\n\n\n\n

    void build(int node, int st, int dr) {\n\n    if(st == dr) {\n        \/\/ nodul curent descrie un interval de lungime 1\n\n        tree[node] = v[st]; \/\/ prelu\u0103m valoarea din vector\n        return;\n\n    }\n    \n    \/\/ \u00eemp\u0103r\u021bim intervalul curent \u00een doua subintervale\n    int mid = (st + dr) \/ 2;\n    build(2 * node, st, mid); \/\/mergem \u00een nodul din st\u00e2nga \u0219i construim primul subinterval\n    build(2 * node + 1, mid + 1, dr); \/\/ mergem \u00een nodul din dreapta \u0219i construim al doilea subinterval\n    \n    tree[node] = tree[2 * node] + tree[2 * node + 1]; \/\/ rezultatul pentru intervalul curent\n\n}<\/pre>\n\n\n\n
    \n
      \n
    • Actualizarea unui element \u00een O(log2(N))<\/strong><\/li>\n<\/ul>\n<\/div><\/div>\n\n\n\n
      Vom decide, pentru o pozi\u021bie dat\u0103 din \u0219ir, dac\u0103 ne mut\u0103m \u00een nodul din st\u00e2nga sau dreapta, \u00een func\u021bie de subintervalele asociate nodurilor. \u00cen acest mod, vom ajunge s\u0103 actualiz\u0103m rezultatele \u00een timp logaritmic.<\/p>\n\n\n\n
      void update(int node, int st, int dr, int poz, int val){\n\n    if(st == dr){\n\n        \/\/ am ajuns \u00een nodul corespunz\u0103tor pozi\u021biei care-\u0219i schimb\u0103 valoarea\n        tree[node] = val;\n        return;\n\n    }\n\n    int mid = (st + dr) \/ 2;\n\n    if(poz <= mid)\n \/\/ dac\u0103 pozi\u021bia pe care o caut\u0103m se afl\u0103 \u00een primul subinterval, vom merge \u00een nodul corespunz\u0103tor\n        update(2 * node, st, mid, poz, val);\n\n    if(poz > mid) \/\/ dac\u0103 pozi\u021bia pe care o caut\u0103m se afl\u0103 \u00een al doilea subinterval, vom merge \u00een nodul corespunz\u0103tor\n        update(2 * node + 1, mid + 1, dr, poz, val);\n\n    tree[node] = tree[2 * node] + tree[2 * node + 1]; \/\/ refacem rezultatele din cauza modific\u0103rii aduse\n\n}<\/pre>\n\n\n\n
      Dac\u0103 vrem s\u0103 modific\u0103m, de exemplu, valoarea de la pozi\u021bia 4, vom merge \u00een nodurile:<\/p>\n\n\n\n
        \n
      1. 1<\/strong>, care descrie intervalul [1, 7]<\/em><\/li>\n\n\n\n
      2. 2<\/strong>, care descrie intervalul [1, 4]<\/em><\/li>\n\n\n\n
      3. 5<\/strong>, care descrie intervalul [3, 4]<\/em><\/li>\n\n\n\n
      4. 11<\/strong>, care descrie intervalul [4, 4]<\/em>, unde vom schimba valoarea asociata nodului cu parametrul val<\/strong><\/li>\n<\/ol>\n\n\n\n
        \n
        \"\"<\/figure>\n<\/figure>\n\n\n\n
          \n
        • Interogarea unui interval \u00een O(log2(N))<\/strong><\/li>\n<\/ul>\n\n\n\n
          Vom \u00eencerca s\u0103 descompunem intervalul despre care dorim s\u0103-i afl\u0103m suma \u00een subintervale disjuncte din arbore. Formal, vom descompune un interval [x, y]<\/strong> \u00een intervale de forma [x, y1], [y1 + 1, y2], [y2 + 1, y3], …, [yn + 1, y].<\/strong> De exemplu, intervalul [2, 5]<\/em> se descompune \u00een: [2, 2], [3, 4], [5, 5].<\/em> Fiecare interval se va descompune \u00een cel mult 2[log2(N)] <\/em>intervale. R\u0103spunsul interog\u0103rii va fi suma valorilor din nodurile ale c\u0103ror reuniune de intervale asociate d\u0103 exact intervalul [x, y].<\/em><\/p>\n\n\n\n
          int query(int node, int st, int dr, int x, int y){\n\n    if(x <= st && dr <= y) \/\/ m\u0103 aflu \u00eentr-un subinterval care este inclus in intervalul de interogare( de exemplu, [3, 4] este inclus in [2,5])\n        return tree[node];\n\n    int mid = (st + dr) \/ 2, r1 = 0, r2 = 0;\n\n    if(x <= mid) \/\/ dac\u0103 mai exist\u0103 o por\u021biune din intervalul de interogare \u00een primul subinterval, preiau rezultatul\n        r1 = query(2 * node, st, mid, x, y);\n\n    if(y > mid) \/\/ dac\u0103 mai exist\u0103 o por\u021biune din intervalul de interogare \u00een al doilea subinterval, preiau rezultatul\n        r2 = query(2 * node + 1, mid + 1, dr, x, y);\n\n    return r1 + r2; \/\/ combin rezultatele\n\n}<\/pre>\n\n\n\n
          Pentru intervalul de interogare [2, 5]<\/em>, avem:<\/p>\n\n\n\n
            \n
          1. Nodul 1<\/strong> cu intervalul [1, 7]<\/em> care nu este inclus \u00een [2, 5]<\/em>, deci \u00eel vom \u00eemp\u0103r\u021bi \u0219i verific\u0103m dac\u0103 subintervalele rezultate se suprapun<\/strong> cu [2, 5]<\/em>. Subintervalele sunt [1, 4]<\/em> \u0219i [5, 7]<\/em>, deci vom merge \u00een ambele, pe r\u00e2nd;<\/li>\n\n\n\n
          2. Nodul 2<\/strong> cu intervalul [1, 4]<\/em> care nu este inclus \u00een [2, 5]<\/em>, deci aplic\u0103m acela\u0219i procedeu ca mai sus. Subintervalele sunt [1, 2]<\/em> \u0219i [3, 4]<\/em>, deci, din nou, vom merge \u00een ambele;<\/li>\n\n\n\n
          3. Nodul 4<\/strong> cu intervalul [1, 2] <\/em>care nu este inclus \u00een [2, 5]<\/em>. Subintervalele sunt [1, 1]<\/em> \u0219i [2, 2]<\/em>. Decidem deci s\u0103 mergem doar \u00een intervalul [2, 2]<\/em>, fiind singurul care se suprapune cu [2, 5]<\/em>;<\/li>\n\n\n\n
          4. Nodul 9<\/strong> cu intervalul [2, 2]<\/em>. Este un interval inclus \u00een [2, 5]<\/em>, deci adun\u0103m valorea din nod => 3<\/span><\/em><\/strong>;<\/li>\n\n\n\n
          5. Revenim din [2, 2]<\/em> \u00een [1, 2]<\/em>, apoi \u00een [1, 4]<\/em> \u0219i mergem \u00een nodul 5<\/strong> cu intervalul asociat [3, 4]<\/em>, care este inclus \u00een [2, 5]<\/em>, deci vom aduna valorea din nou => 1<\/span><\/em><\/strong>;<\/li>\n\n\n\n
          6. Revenim din [3, 4]<\/em> \u00een [1, 4]<\/em>, pentru care rezultatul este 1 + 3 = 4 (suma elementelor intervalului rezultat din suprapunerea lui [2, 5] cu [1, 4])<\/strong>, apoi \u00een [1, 7]<\/em>. Mergem \u00een nodul 3<\/strong> cu intervalul asociat [5, 7]<\/em>, care nu este inclus \u00een [2, 5]<\/em>. Subintervalele sunt [5, 6]<\/em> \u0219i [7, 7]<\/em>. Singurul care se suprapune cu [2, 5]<\/em> este [5, 6]<\/em>.<\/li>\n\n\n\n
          7. Nodul 6<\/strong> cu intervalul [5, 6]<\/em> care nu este inclus \u00een [2, 5]<\/em>. Subintervalele sunt [5, 5]<\/em> \u0219i [6, 6]<\/em>. Decidem s\u0103 mergem doar \u00een intervalul [5, 5]<\/em>.<\/li>\n\n\n\n
          8. Nodul 12<\/strong> cu intervalul [5, 5]<\/em> care este inclus \u00een [2, 5]<\/em>, deci adun\u0103m valorea din nod => 9<\/span><\/strong><\/em>;<\/li>\n\n\n\n
          9. Revenim din [5, 5]<\/em> \u00een [5, 6]<\/em>, pentru care rezultatul este 9 (suma elementelor intervalului rezultat din suprapunerea lui [2, 5] cu [5, 6])<\/strong>, apoi \u00een [5, 7]<\/em> (cu acela\u0219i rezultat) \u0219i \u00een final \u00een [1, 7]<\/em>, pentru care avem rezultatul 4 + 9 = 13 (suma elementelor din [2, 5])<\/strong>.<\/li>\n<\/ol>\n\n\n\n
            <\/p>\n\n\n\n
              \n
            • Actualizarea unui interval de elemente \u00een O(log2(N))) – lazy update<\/strong><\/li>\n<\/ul>\n\n\n\n
              Dac\u0103 dorim s\u0103 actualiz\u0103m un anumit interval de elemente\/pozi\u021bii din vector, o abordare ca cea de mai sus ne va duce la  o complexitate prea mare (este ineficient pentru un interval [x, y]<\/em> pe care vrem s\u0103-l actualiz\u0103m cu o valoare val<\/strong>, s\u0103 parcurgem fiecare pozi\u021bie din acel interval). Ca urmare, vom folosi tehnica „lazy update”<\/em>, care se refer\u0103 la propagarea actualiz\u0103rilor de la cele mai mari intervale incluse \u00een [x, y]<\/em> spre fiii lor, \u00een jos. Pe l\u00e2ng\u0103 arborele de intervale principal, \u00een care re\u021binem rezultatele, vom construi un al doilea arbore de intervale care ne va ajuta s\u0103 re\u021binem cu ce valoare trebuie s\u0103 actualiz\u0103m elementele din intervalul asociat unui nod. Dup\u0103 ce actualiz\u0103m elementele, vom „propaga” valoarea de actualizare, re\u021binut\u0103 \u00een al doilea arbore (ex: lazy[node])<\/strong> c\u0103tre fii, adic\u0103 lazy[2 * node], respectiv lazy[2 * node + 1], \u0219i vom pierde valoarea din lazy[node] (eliber\u0103m lazy[node] de toate actualiz\u0103rile necesare intervalului pe care-l descrie „node”, \u00eentruc\u00e2t le-am trimis fiilor lui).<\/strong><\/p>\n\n\n\n
              Aceast\u0103 opera\u021bie poate fi vizualizat\u0103 mai jos, unde este prezentat arborele de intervale lazy[]<\/strong>, \u00eenainte \u0219i dup\u0103 propagarea valorii (adic\u0103 5<\/em>) cu care trebuie actualizat intervalul [3, 4]<\/em>:<\/p>\n\n\n\n
              \"\"
              \u00eenainte de propagare<\/figcaption><\/figure>\n\n\n\n
              \"\"
              dup\u0103 propagare<\/figcaption><\/figure>\n\n\n\n
              Func\u021bia care ne ajut\u0103 s\u0103 actualiz\u0103m rezultatele folosind arborele lazy[]<\/strong> arat\u0103 astfel:<\/p>\n\n\n\n
              void update_lazy(int node, int st, int dr){\n\n    \/\/ aten\u021bie! vectorul lazy[]<\/strong> trebuie ini\u021bializat \u00een totalitate cu -1 \u00eenaintea efectu\u0103rii oric\u0103rei opera\u021bii pe arbore pentru a se p\u0103stra proprietatea de mai jos\n\n    if(lazy[node] == -1) \/\/ nu avem nimic de actualizat \u00een intervalul curent (putem folosi o alt\u0103 valoare care NU se afl\u0103 \u00een intervalul valorilor posibile la actualizare)\n        return;\n\n    tree[node] = (dr - st + 1) * lazy[node]; \/\/ actualiz\u0103m rezultatele din nodul curent cu valoarea de actualizare * c\u00e2te elemente sunt \u00een interval, \u00eentruc\u00e2t fiecare element se modific\u0103\n\n    if(st != dr){ \/\/ exist\u0103 fii\n\n       \n        \/\/ trimitem valoarea cu care actualiz\u0103m c\u0103tre fiii nodului curent\n        lazy[2 * node] = lazy[node];\n        lazy[2 * node + 1] = lazy[node];\n\n    }\n\n    lazy[node] = -1; \/\/ pierdem valoarea cu care actualiz\u0103m\n\n}<\/pre>\n\n\n\n
              Ca urmare, func\u021bia de actualizare va suferi modific\u0103ri:<\/p>\n\n\n\n
              void update(int node, int st, int dr, int x, int y, int val){\n\n    \/\/ verific\u0103m dac\u0103 trebuie s\u0103 actualiz\u0103m intervalul curent cu o anumit\u0103 valoare\n    update_lazy(node, st, dr);\n\n    if(x <= st && dr <= y){\n        \n        \/\/ m\u0103 aflu \u00eentr-un interval inclus \u00een intervalul de actualizat (unul dintre intervalele de lungime maxim\u0103 din arbore care este inclus \u00een [x, y] - intervalul de actualizat)<\/em>\n\n        lazy[node] = val; \/\/ modific cu actualizarea curent\u0103\n        update_lazy(node, st, dr); \/\/ voi propaga actualizarea c\u0103tre fii\n\n        return;\n\n    }\n\n    int mid = ((st + dr) >> 1);\n\n    if(x <= mid)\n        update(2 * node, st, mid, x, y, val);\n\n    if(y > mid)\n        update(2 * node + 1, mid + 1, dr, x, y, val);\n\n     \n    \/\/ acum vom propaga eventualele rezultate din fii c\u0103tre urm\u0103toarele noduri\n    update_lazy(2 * node, st, mid);\n    update_lazy(2 * node + 1, mid + 1, dr);\n\n    tree[node] = tree[2 * node] + tree[2 * node + 1]; \/\/ refacem rezultatele\n\n}<\/pre>\n\n\n\n
              ATEN\u021aIE: dup\u0103 cum se observ\u0103, update_lazy() \u0219i update() sunt func\u021bii diferite! <\/strong><\/p>\n\n\n\n
                \n
              • update() ajut\u0103 la actualizarea intervalelor de lungime maxim\u0103 din arbore care sunt incluse \u00een intervalul de actualizat;<\/strong><\/li>\n\n\n\n
              • update_lazy() ajut\u0103 la propagarea rezultatelor.<\/strong><\/li>\n<\/ul>\n\n\n\n
                Interog\u0103rile vor ar\u0103ta un pic diferit: la fel ca func\u021bia de actualizare, \u00eenainte s\u0103 return\u0103m un rezultat dintr-un nod, verific\u0103m dac\u0103 trebuie actualizat cu o anumit\u0103 valoare.<\/p>\n\n\n\n
                int query(int node, int st, int dr, int x, int y){\n\n    \n    \/\/ verific\u0103m dac\u0103 este nevoie de actualiz\u0103ri ale rezultatelor\n    update_lazy(node, st, dr);\n\n    if(x <= st && dr <= y)\n        return tree[node];\n\n    int mid = (st + dr) \/ 2, r1 = 0, r2 = 0;\n\n    if(x <= mid)\n        r1 = query(2 * node, st, mid, x, y);\n\n    if(y > mid)\n        r2 = query(2 * node + 1, mid + 1, dr, x, y);\n\n    return r1 + r2;\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":"
                Un arbore de intervale este o structur\u0103 de date similar\u0103 cu un arbore binar, \u00een care fiecare nod con\u0163ine informa\u0163ii … <\/p>\n","protected":false},"author":3,"featured_media":479,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-458","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\/458","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=458"}],"version-history":[{"count":23,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/458\/revisions"}],"predecessor-version":[{"id":496,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/458\/revisions\/496"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/479"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=458"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=458"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=458"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}