infoarena

Comentarii la articolul Arbori de intervale si aplicatii in geometria computationala (http://infoarena.ro/arbori-de-intervale)

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:

Apelez aceasta functie din Main astfel:
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:

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:
asa:

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.

Stiu ca e irelevant, dar totusi...

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

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 ?

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!