Arbori de intervale
Un arbore de intervale este un arbore binar complet în care în fiecare nod reţinem răspunsul pentru un anumit interval. Considerăm
vectorul tree de dimensiune $4 * N$, în care dorim să efectuăm operaţiile de $update$ şi $query$. Rădăcina va reţine răspunsul pentru intervalul $[1, n]$. Pentru fiecare nod reţinem răspunsul pentru intervalul $[st, dr]$, unde $st$ <= $dr$, iar fiul din stânga va reţine răspunsul pentru intervalul $[st, mij]$, pe când fiul din dreapta răspunsul pentru intervalul $[mij + 1, dr]$, unde $mij = (st + dr) / 2$.
Intervalul $[st, dr]$ asociat unui nod se numeşte interval standard. Frunzele arborelui sunt considerate intervale elementare, ele având lungimea $1$.
Proprietăţi:
Un arbore de intervale este un arbore binar echilibrat (diferenţa absolută între adâncimea subarborelui stâng îi cea a subarborelui drept este cel mult $1$). Astfel, adâncimea unui arbore de intervale care conţine intervale incluse în $[1, N]$ este $[\log_2 n]$ + $1$, şi tocmai din acest motiv timpul de execuţie pentru operaţiile de update, respectiv query este de
$O(\log_2 n)$.
Un arbore de intervale necesită memorie de $4 * N$.
Dacă valoarea nodului care reţine intervalul $[st, dr]$ este $node$, valoarea nodului care reţine fiul din stânga este $2 * node$, iar valoarea nodului care reţine fiul din dreapta este $2 * node + 1$.
![](exemplu.png)
Update
-
Începem să căutăm din rădăcină poziţia elementului pe care trebuie să-l actualizăm. În funcţie de intervalul care conţine poziţia căutată ne deplasăm fie pe fiul din stânga, fie pe cel din dreapta. Odata ce am ajuns în frunză, actualizăm valoarea poziţiei şi utilizăm o abordare de tipul $bottom-up$ până la rădăcină, pentru a schimba şi valoarea intervalelor în care se află poziţia modificată.
Query
-
Căutăm răspunsul la un query pe intervalul $[x, y]$, astfel: recursiv din rădăcină începem să verificăm dacă intervalul reprezentat de nodul actual se află complet în intervalul căutat. Dacă da, returnăm valoarea nodului.
Lazy update
-
Folosim lazy update în momentul în care trebuie să modificăm valoarea din fiecare poziţie din intervalul $[st, dr]$, pentru a nu risca ca un update care în mod normal se face în $O(\log_2 n)$, să-l facem în $O(n\log_2 n)$. Astfel vom mai folosi un vector, $lazy$, în care vom reţine că trebuie sa modificăm valorile din intervalul $[st, dr]$, iar când vom avea nevoie de valoarea unei poziţii din intervalul $[st, dr]$, vom propaga $lazy-ul$ la cei $2$ fii până ajungem la poziţia căutată.
|