h2. Enunt

In continuare voi prezenta enuntul unui tip de problema ce a aparut la multe dintre concursurile de informatica. Motivul pentru care am ales acest lucru este ca unii participanti pot fi tentati sa incerce sa adapteze rezolvarea acesteia la rezolvarea problemei ce necesita _heavy path decomposition_. Lucru ce nu este posibil, pierzand astfel timp pretios. Iata enuntul:

In continuare voi prezenta enuntul unui tip de problema ce a aparut la multe dintre concursurile de informatica. Motivul pentru care am ales acest lucru este ca unii participanti pot fi tentati sa incerce sa adapteze rezolvarea acesteia la rezolvarea problemei ce necesita _heavy path decomposition_, lucru ce nu este posibil, pierzandu-se astfel timp pretios. Iata enuntul:

Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$ (pe scurt, un arbore). Vom considera ca fiecare nod $x &#8712; V$ are asociata o valoare $value[x]$ din multimea numerelor reale. Se dau $M$ instructiuni, $M <= 200000$, de doua tipuri:

==
Functia $QUERYAi(Path[], lo, hi)$ returneaza in $O(log(N))$, cu ajutorul structurii de date arbori de intervale, maximul dintre valorile cuprinse in intervalul $[lo, hi]$.
Raspunsul cerintei de primul tip va fi  {$Maxim(QUERY (lca, x), QUERY (lca, y))$}, variabila $lca$ fiind cel mai apropiat stramos comun al lui $x$ si $y$.

Pentru rezolvarea cerintei de tipul doi, vom folosi aceeasi arbori de intervale care vor obtine un cost de $O(log(N))$ per operatie. Nu voi prezenta aceasta functie aici, ea fiind in detaliu prezentata in una din sursele afisate in Bibliografie.

Pentru rezolvarea cerintei de tipul doi, vom folosi aceiasi arbori de intervale care vor obtine un cost de $O(log(N))$ pe operatie. Nu voi prezenta aceasta functie, ea fiind in detaliu prezentata in una din sursele afisate in Bibliografie.

Complexitatea finala: $O(M*sqrt(N)*log(N))$. Cel mai rau caz pentru un query este cand se trece prin toate lanturile (in numar de $sqrt(N)$) efectuandu-se cate un query pe fiecare arbore de intervale asociat ({$O(log(N))$}).