h1. 'Treesmen':problema/treesmen

Vom face o liniarizare a arborelui, cu ajutorul căreia vom efectua eficient cele două operaţii. Soluţia se bazează pe prima idee care ne vine în minte, adică, pentru prima operaţie facem update pe intervalul $[first[stramos], first[node]]$ şi pentru a doua căutam ce valoare avem pe poziţia $first[node]$; dar, s-ar putea, ca la update să avem noduri care nu se află pe lanţ dar apar şi în interval. Plecând de la această observaţie ajungem la observaţia : aceste noduri vor avea $first-ul si last-ul$ incluse în $[first[stramos], first[node]]$. Astfel putem defini în $last[node] = suma valorilor când node nu apare pe lanţ.$ Făcând această observaţie răspunsul pentru un query va fi $valoarea de pe poziţia first[node] - valoarea de pe poziţia last[node]$. Update-ul e o progresie arimetica, aşa că, nodul $X$ o să crească cu valoarea $p + (nivel[X] - nivel[stramos])*r.$ Dacă desfacem paranteza şi grupăm termenii convenabil obţinem $p-nivel[stramos]*r + nivel[X]*r$. Astfel, problema se rezumă la a face update pe un interval cu o valoare $X$; ne putem folosi de arbori de intervale sau arbori indexati binar pentru a face acest lucru.

Vom face o liniarizare a arborelui, cu ajutorul căreia vom efectua eficient cele două operaţii. Soluţia se bazează pe prima idee care ne vine în minte, adică, pentru prima operaţie facem update pe intervalul $[first[stramos], first[node]]$ şi pentru a doua căutam ce valoare avem pe poziţia $first[node]$; dar, s-ar putea, ca la update să avem noduri care nu se află pe lanţ dar apar şi în interval.
 
Plecând de la această observaţie vom ajunge la altă observaţie: aceste noduri vor avea $first-ul si last-ul$ incluse în $[first[stramos], first[node]]$. Astfel putem defini:
 
* $last[node] = suma valorilor când node nu apare pe lanţ.$
 
Făcând această observaţie răspunsul pentru un query va fi $valoarea de pe poziţia first[node] - valoarea de pe poziţia last[node]$. Update-ul e o progresie arimetica, aşa că, nodul $X$ o să crească cu valoarea $p + (nivel[X] - nivel[stramos])*r.$ Dacă desfacem paranteza şi grupăm termenii convenabil obţinem $p-nivel[stramos]*r + nivel[X]*r$. Astfel, problema se rezumă la a face update pe un interval cu o valoare $X$; ne putem folosi de arbori de intervale sau arbori indexati binar pentru a face acest lucru.
 

Complexitate $O(M * log N).$

==include(page="template/monthly-2014/footer")==