Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Arbori de intervale si aplicatii in geometria computationala  (Citit de 5813 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« : Februarie 20, 2009, 02:37:51 »

Comentarii la articolul Arbori de intervale si aplicatii in geometria computationala
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #1 : 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  Very Happy 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.
« Ultima modificare: Septembrie 24, 2010, 15:27:53 de către Marginean Ciprian » Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #2 : Februarie 20, 2011, 18:40:00 »

Citat
Actualizarea unui interval intr-un arbore de intervale
Stiu ca e irelevant, dar totusi...
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #3 : Februarie 20, 2011, 23:37:12 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
sfarma_pietre
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #4 : 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 ?
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #5 : 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!
« Ultima modificare: Februarie 20, 2013, 19:06:06 de către Pirtoaca George Sebastian » Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines