infoarena

infoarena - concursuri, probleme, evaluator, articole => Articole => Subiect creat de: Stefan Istrate din Februarie 20, 2009, 02:37:51



Titlul: Arbori de intervale si aplicatii in geometria computationala
Scris de: Stefan Istrate din Februarie 20, 2009, 02:37:51
Comentarii la articolul Arbori de intervale si aplicatii in geometria computationala (http://infoarena.ro/arbori-de-intervale)


Titlul: Răspuns: Arbori de intervale si aplicatii in geometria computationala
Scris de: MciprianM din Septembrie 23, 2010, 21:37:06
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  :D 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.


Titlul: Răspuns: Arbori de intervale si aplicatii in geometria computationala
Scris de: George Marcus din Februarie 20, 2011, 18:40:00
Citat
Actualizarea unui interval intr-un arbore de intervale
Stiu ca e irelevant, dar totusi...


Titlul: Răspuns: Arbori de intervale si aplicatii in geometria computationala
Scris de: Andrei Grigorean din Februarie 20, 2011, 23:37:12
Pagina e wiki, daca mai gasesti astfel de greseli nu te sfii sa le repari singur :ok:


Titlul: Răspuns: Arbori de intervale si aplicatii in geometria computationala
Scris de: Octavian Ganea din Februarie 20, 2013, 16:36:55
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 ?


Titlul: Răspuns: Arbori de intervale si aplicatii in geometria computationala
Scris de: Pirtoaca George Sebastian din Februarie 20, 2013, 18:47:24
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!