Lazy propagation

[•stardust]

Am incercat sa invat arbori de intervale dar imi e cam greu sa ii inteleg. Voiam sa implementez o sursa in care cresteam valorile dintr-un interval [x,y] cu un anumita valoare iar apoi aveam query suma de pe un interval. Am intrebat pe topicul din arhiva educationala si Mircea Dima mi-a spus despre tehnica lazy update/propagation. Mi-a dat chiar si o sursa demonstrativa. Sincer nu prea am inteles asa ca am cautat pe net dar spre surprinderea mea nu se gasesc chiar asa multe. Ideea cred ca am inteles-o. Adica faci update doar cand e nevoie. De exemplu daca trebuie sa fac update pe [1,10] updatez doar nodul ala si tin o informatie in plus care imi zice ca trebuie sa ii updatez si fii. Cand am query pe un interval mai adanc si dau de un nod din asta il updatez si ii marchez fii. E corect ? Desi nu pare mare filosofie cand vine vorba sa implementez ma incruc rau de tot. De asta as vrea sa vad voi cum implementati. M-ar ajuta mult niste cod. Si inca ceva, daca as vrea query de maxim/minim se modifica cumva functia de update ?

[•deneo]

Uite-te pe sursele de la problema http://infoarena.ro/problema/hotel