{@ADUNA(st, dr, x)@} - toate elementele cu indicii intre $st$ si $dr$ isi cresc valoarea cu $x$
{@SUMA(st, dr)@} - returneaza suma elementelor cu indicii intre $st$ si $dr$
Pentru cei ce cunosc arbori de intervale, rezolvarea acestei probleme in $O(lg n)$ per operatie este o munca usoara, dar presupunand ca nu stim aceasta structura putem folosi urmatorul truc: vom construi un al doilea vector de lungime $sqrt(n)$ care retine suma elementelor pe bucati de lungime {$sqrt(n)$}. Pentru a face o operatie pe un interval [{$st, dr$}] vom imparti acest interval in bucati de $sqrt(n)$ a caror actualizare o facem in vectorul $B$ si elementele care raman in margine in vectorul {$A$}. De exemplu pe vectorul {@A[0..15]@} vom avea vectorul {@B[0..3]@}. Pentru a actualiza de exemplu [{$2, 12$}] vom actualiza {@B[1]@} (care corespunde lui [{$4..7$}]), {@B[2]@} (pentru [{$8..11$}]) si {@A[2]@}, {@A[3]@}, {@A[12]@} (elementele din margini). Cum sunt maxim $sqrt(n)$ elemente de actualizat in $B$ si pe margini nu vom actualiza niciodata mai mult de $2 * sqrt(n)$ elemente putem concluziona ca operatiile vor avea complexitate {$O(sqrt(n))$}.
Pentru cei ce cunosc arbori de intervale, rezolvarea acestei probleme in $O(lg n)$ per operatie este o munca usoara, dar presupunand ca nu stim aceasta structura putem folosi urmatorul truc: vom construi un al doilea vector de lungime $sqrt(n)$ care retine suma elementelor pe bucati de lungime {$sqrt(n)$}. Pentru a face o operatie pe un interval [{$st, dr$}] vom imparti acest interval in bucati de $sqrt(n)$ a caror actualizare o facem in vectorul $B$ si elementele care raman in margine in vectorul {$A$}. De exemplu pe vectorul {$A{~0..15~}$} vom avea vectorul {$B{~0..3~}$}. Pentru a actualiza de exemplu [{$2, 12$}] vom actualiza {$B{~1~}$} (care corespunde lui [{$4..7$}]), {$B{~2~}$} (pentru [{$8..11$}]) si {$A{~2~}$}, {$A{~3~}$}, {$A{~12~}$} (elementele din margini). Cum sunt maxim $sqrt(n)$ elemente de actualizat in $B$ si pe margini nu vom actualiza niciodata mai mult de $2 * sqrt(n)$ elemente putem concluziona ca operatiile vor avea complexitate {$O(sqrt(n))$}.
Daca am avea aceeasi problema dar in doua dimensiuni, am putea face acelasi "smen" pentru fiecare linie pentru o complexitate $O(n*sqrt(n))$ per operatie, sau cu arbori de intervale pe fiecare linie {$O(n*lg n)$}. Putem, de asemenea obtine o complexitate $O(n)$ folosind urmatoarea impartire:
$A$ - pentru bucati $1 * 1$
Operatia de LCA se va realiza apoi foarte usor, urcand pe tatii din intervale, pana se ajunge la doua noduri in acelasi interval, apoi folosindu-se metoda clasica. Cod:
int LCA(int x, int y)
{
while (T2[x] != T2[y])
if (Lev[x] > Lev[y])
x = T2[x];
else
y = T2[y];
while (x != y)
if (Lev[x] > Lev[y])
x = T[x];
else
y = T[y];
return x;
}
p(pre).
{@int LCA(int x, int y)@}
{@{@}
{@ while (T2[x] != T2[y])@}
{@ if (Lev[x] > Lev[y])@}
{@ x = T2[x];@}
{@ else@}
{@ y = T2[y];@}
{@ while (x != y)@}
{@ if (Lev[x] > Lev[y])@}
{@ x = T[x];@}
{@ else@}
{@ y = T[y];@}
{@ return x;@}
{@}@}
h2. LCA in O(lg^2 n)
h2. LCA in $O(lg^2^ n)$
Aceeasi problema, dar o alta rezolvare. Vom construi o matrice A[i][j] cu semnificatia A[i][j] = al 2^i-lea tata al nodului j. Folosind aceasta matrice putem cauta binar (O(lg n)) nivelul pe care s-ar putea afla LCA-ul a doua noduri si sa determinam daca nodul ales este corect - adica daca nodul situat la acel nivel este acelasi pentru cele doua noduri pentru care se face LCA (O(lg n) cu matricea de mai sus). Complexitate finala O(lg^2 n) si O(n*lg n) memorie.
Aceeasi problema, dar o alta rezolvare. Vom construi o matrice $A{~i,j~}$ cu semnificatia $A{~i,j~}$ = al {$2^i^$}-lea tata al nodului {$j$}. Folosind aceasta matrice putem cauta binar ({$O(lg n)$}) nivelul pe care s-ar putea afla LCA-ul a doua noduri si sa determinam daca nodul ales este corect - adica daca nodul situat la acel nivel este acelasi pentru cele doua noduri pentru care se face LCA ({$O(lg n)$} cu matricea de mai sus). Complexitate finala $O(lg^2^ n)$ si $O(n*lg n)$ memorie.
h2. For-uri "complicate"
for-ul in C/C++ este foarte flexibil si poate ajuta foarte mult in compactarea codului, deci si a timpului de implementare. In continuare vom prezenta algoritmul merge sort (sortare prin interclasare) scris in cateva linii (putine, zic eu!):
int N, A[N], B[N];
void merge_sort(int l, int r)
{
int m = (l + r) >> 1, i, j, k;
if (l == r) return;
merge_sort(l, m);
merge_sort(m + 1, r);
for (i=l, j=m+1, k=l; i<=m || j<=r; )
if (j > r || (i <= m && A[i] < A[j]))
B[k++] = A[i++];
else
B[k++] = A[j++];
for (k = l; k <= r; k++) A[k] = B[k];
}
p(pre).
{@int N, A[N], B[N];@}
{@void merge_sort(int l, int r)@}
{@{@}
{@ int m = (l + r) >> 1, i, j, k;@}
{@ if (l == r) return;@}
{@ merge_sort(l, m);@}
{@ merge_sort(m + 1, r);@}
{@ for (i=l, j=m+1, k=l; i<=m || j<=r; )@}
{@ if (j > r || (i <= m && A[i] < A[j]))@}
{@ B[k++] = A[i++];@}
{@ else@}
{@ B[k++] = A[j++];@}
{@ for (k = l; k <= r; k++) A[k] = B[k];@}
{@}@}
h2. Recomandari generale
I. Programare dinamica cu memoizare: mult mai simplu si uneori chiar mai rapida cand nu ne trebuie tot array-ul
II. Algoritmi randomizati: de multe ori mai usor de implementat si mai eficienti, mai bine decat cei euristici, dar necesita o analiza mult mai atenta a performantei. Exemple calsice: quciksort, statistici de ordine
# Programare dinamica cu memoizare: mult mai simplu si uneori chiar mai rapida cand nu ne trebuie tot array-ul
# Algoritmi randomizati: de multe ori mai usor de implementat si mai eficienti, mai bine decat cei euristici, dar necesita o analiza mult mai atenta a performantei. Exemple calsice: quciksort, statistici de ordine
h2. "Smenul lui Mars" (Marius Andrei)
Consideram urmatoarea problema: se da un vector A de N elemente pe care se fac M astfel de operatii: ADUNA(st, dr, x) - toate elementele cu indicii intre st si dr isi cresc valoarea cu x. La sfarsit trebuie sa se afiseze vectorul rezultat. In continuarea vom descrie o metoda care ne da un timp de rulare de O(1) pentru operatia ADUNA si O(N) pentru a determina un element din vector. Vom construi un al doilea vector B de N+1 elemente, cu proprietatea ca A[i] = B[0] + B[1] + ... B[i]. Astfel, o operatie ADUNA(st, dr, x) devine:
Consideram urmatoarea problema: se da un vector $A$ de $N$ elemente pe care se fac $M$ astfel de operatii: {@ADUNA(st, dr, x)@} - toate elementele cu indicii intre $st$ si $dr$ isi cresc valoarea cu {$x$}. La sfarsit trebuie sa se afiseze vectorul rezultat. In continuarea vom descrie o metoda care ne da un timp de rulare de $O(1)$ pentru operatia $ADUNA$ si $O(N)$ pentru a determina un element din vector. Vom construi un al doilea vector $B$ de $N+1$ elemente, cu proprietatea ca {$A{~i~} = B{~0~} + B{~1~} + ... B{~i~}$}. Astfel, o operatie ADUNA(st, dr, x) devine:
B[st] += x;
B[dr + 1] -= x;
