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:
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:
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:
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:
if (nod<0||nod>=4*MAXN+66) return;
asa:
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.