Vom formula aici o posibilă cerință: Pentru un interval [st, dr] și o valoarea val, să se adune la toate elementele din interval valoarea val.
Funcția va avea 6 parametri (nod, Lnod, Rnod, st, dr, val).
Pentru a putea rezolva această problemă este necesară reținerea unui vector în plus, pe lângă cel care reține răspunsurile din arborele de intervale. Vom nota acest vector cu "lazy".
Observăm că dacă vrem să modificăm un interval prin funcția de update, în cel mai rău caz se vor parcurge de N ori câte log2(N) noduri.
Totuși, este nevoie să facem asta? Răspuns evident: NU.
Asemănător funcției de query, vom parcurge arborele începând cu rădăcina și:
1. dacă suntem la un nod al cărui interval de acoperire este inclus complet în [st, dr], adăugăm val la lazy[nod].
2. altfel, vom continua parcurgerea în nodurile care au intersecția dintre intervalul de acoperire și [st, dr] nevidă.
Apoi, mereu când coborâm în arbore prin intermediul altor apeluri, vom propaga informația de la nod, către fii, iar în momentul propagării vom goli lazy[nod], nu înainte să adunăm informația în aint[nod]. Astfel, în cazul unei probleme care necesită lazy update, se vor modifica și funcțiile prezentate anterior.
Având în vedere comportamentul similar cu funcția de query, complexitatea funcției "lazy update" va fi O(log(N)).
int get_value(int nod) ///functie care returneaza valoarea din nod
{
return aint[nod]+lazy[nod];
}
void prp(int nod, int st, int dr)
{
aint[nod]=get_value(nod);
if(st!=dr)
{
lazy[2*nod]+=lazy[nod];
lazy[2*nod+1]+=lazy[nod];
}
lazy[nod]=0;
}
void lazy_update(int nod, int st, int dr, int ust, int udr, int val)
{
prp(nod, st, dr);
if(st>=ust && dr<=udr)
{
lazy[nod]+=val;
return;
}
int mij=(st+dr)/2;
if(ust<=mij) lazy_update(2*nod, st, mij, ust, udr, val);
if(udr>mij) lazy_update(2*nod+1, mij+1, dr, ust, udr, val);
aint[nod]=min(get_value(2*nod), get_value(2*nod+1));
}
int query(int nod, int st, int dr, int qst, int qdr)
{
prp(nod, st, dr);
if(st>=qst && dr<=qdr) return aint[nod];
int mij=(st+dr)/2, ms=1e9, md=1e9;
if(qst<=mij) ms=query(2*nod, st, mij, qst, qdr);
if(qdr>mij) md=query(2*nod+1, mij+1, dr, qst, qdr);
return min(ms, md);
}