Arbori de intervale si aplicatii in geometria computationala

[•stef2n]

Comentarii la articolul Arbori de intervale si aplicatii in geometria computationala

[•MciprianM]

Am o problema (probabil una stupida, dar ma rog). Am incercat sa implementez un update pe un arbore de intervale(update pe interval) si iau crash(Stack Overflow) la o problema de pe timus. Daca ma poate ajuta cineva cu un exemplu sau cu o explicatie -ce nu fac bine- as scapa de cateva ore bune de Debug   Asa ca multumesc celui/celei care ma va ajuta. Singura functie recursiva din programul meu e urmatoarea:

Cod:

void update ( int nod, int st, int dr){
    int m;
    if ( A <= st && dr <= B ){
        T [ nod ] . l = X;
        T [ nod ] . r = tim ++;
    }
    else{
        m = ( st + dr ) / 2;
        if ( A <= m )   update ( nod * 2, st, m );
        if ( B > m )    update ( nod* 2 + 1, m + 1, dr );

    }
}

Apelez aceasta functie din Main astfel:

Cod:

update ( 1, 1, n );

Variabila n ia valori intre 2 si 100000. A, B, X si tim sunt variabile globale. tim este la inceputul rularii programului 0 si se modifica doar in aceasta functie. A si B sunt capetele intervalului de actualizat, iar X este valoarea pe care o primesc toate elementele din intervalul [A, B] dintr-un sir. Cand apelez functia update din main are loc inegalitatea st<=A<=B<=dr. T este arborele de intervale:

Cod:

const int MAXN = 100009;
struct pereche{
    int l, r;
};
pereche T[4*MAXN+66];

L.E: In celelalte functii nu am declarate siruri, doar cateva variabile.
L.L.E.:
Am adaugat urmatoarea linie in codul functiei update si am luat Accepted:

Cod:

if (nod<0||nod>=4*MAXN+66)  return;

asa:

Cod:

void update ( int nod, int st, int dr){
    int m;
    if (nod<0||nod>=4*MAXN+66)  return;
    if ( A <= st && dr <= B ){
        T [ nod ] . l = X;
        T [ nod ] . r = tim ++;
    }
    else{
        m = ( st + dr ) / 2;
        if ( A <= m )   update ( nod * 2, st, m );
        if ( B > m )    update ( nod* 2 + 1, m + 1, dr );

    }
}

Tot nu inteleg de ce merge prea adanc functia asta.
L.E.: Am gasit problema. Ziceam: " Cand apelez functia update din main are loc inegalitatea st<=A<=B<=dr". Asta nu era adevarata intotdeauna. Era in problema un caz in care nu trebuia sa fac de loc update si eu il faceam(cu A=B=X=0). Si de aceea intra functia in ciclu infinit.

[•PlayLikeNeverB4]

Actualizarea unui interval intr-un arbore de intervale

Stiu ca e irelevant, dar totusi...

[•wefgef]

Pagina e wiki, daca mai gasesti astfel de greseli nu te sfii sa le repari singur

[•sfarma_pietre]

Cred ca imi scapa mie ceva, dar sa luam exemplul vostru de arbore (prima figura). Daca sa zicem facem update(root, 0, 11, 0 , 11) - update pentru intregul interval [0,11] din root - si apoi facem query(root, 0, 11, 5,6) - query pentru intervalul [5,6] - atunci update-ul va modifica doar nodul root si nu si copiii lui iar query-ul va incerca sa combine informatii din root->right si root>left care nu au fost updatate. In general, daca facem update pentru intregul interval din root nu ar fi corect sa se updateze toate cele 2n noduri din arbore ? Pentru ca apoi putem face query pe un subinterval si sa obtinem o prostie. Sau e un mecanism de lazy evaluation ascuns ?

[•SebiSebi]

Daca vrei sa faci update pe interval si query tot pe interval treaba devine mai complicata(trebuie sa faci lazy update).
Pentru update pe interval si query numai pentru secventa [1,n] consulta problema http://infoarena.ro/problema/biscuiti.
Succes!