{@ return i;@}
{@}@}
Procedura de mai sus face cautarea binara folosind puteri a lui 2 in ordine descrescatoare, practic incerc sa determin fiecare bit al rezultatului.
Procedura de mai sus face cautarea binara folosind puteri a lui $2$ in ordine descrescatoare, practic incerc sa determin fiecare bit al rezultatului.
h2. Impartire in bucati de marime sqrt(n) (cunoscut si ca "smenul lui Bogdan Batog")
h2. Impartire in bucati de marime $sqrt(n)$ (cunoscut si ca "smenul lui Bogdan Batog")
Sa presupunem ca avem un vector de lungime n cu numere reale pe care se fac urmatoarele operatii:
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
{@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
B - pentru bucati sqrt(n) * sqrt(n)
C - pentru bucati 1 * sqrt(n)
D - pentru bucati sqrt(n) * 1
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$
$B$ - pentru bucati $sqrt(n) * sqrt(n)$
$C$ - pentru bucati $1 * sqrt(n)$
$D$ - pentru bucati $sqrt(n) * 1$
Acest mod de reprezentare este o extindere directa a aceluiasi smen in doua dimensiuni. Aceasta idee poate fi folosita si pentru alte operatii: inmultire, minim, maxim, etc. In general, orice se poate rezolva cu acest "smen" se poate obtine la o complexitate mai buna cu arbori de intervale, dar merita sa stiti si aceasta ideea deoarece de multe ori scuteste din efortul de implementare, desi se pierde din viteza... alegerea voastra! ;)
h2. LCA in O(sqrt(n)) (ideea originala de la Radu Berinde)
Daca nu stiti ce este LCA, va recomand sa cititi [1]articolul lui Emilian Miron din cadrul site-ului pentru a va documenta. In continuare vom prezenta un algoritm mai ineficient, dar foarte usor de implementat. Consideram arborele si atribuim fiecarui nod o inaltime. Vom imparti arborele in sqrt(H) intervale in functie de inaltime, unde H e inaltimea maxima (de exemplu la H=9 nodurile cu inaltimi intre 0 si 2 vor forma un interval, [3..5] alt interval si ultimul interval de inaltimi [6..8]). Astfel, pentru fiecare nod, pe langa tatal sau, vom retine si tatal din intervalul de mai sus, printr-o parcurede DF. In continuare, codul:
H se calculeaza inainte sau poate fi constant
T sunt tatii nodului si N numarul de noduri
h2. LCA in $O(sqrt(n))$ (ideea originala de la Radu Berinde)
void DF(int n, int t2, int lev)
{
Daca nu stiti ce este LCA, va recomand sa cititi "articolul":http://www.infoarena.ro/LCA_Lowest_common_ancestor lui Emilian Miron din cadrul site-ului pentru a va documenta. In continuare vom prezenta un algoritm mai ineficient, dar foarte usor de implementat. Consideram arborele si atribuim fiecarui nod o inaltime. Vom imparti arborele in $sqrt(H)$ intervale in functie de inaltime, unde $H$ e inaltimea maxima (de exemplu la $H=9$ nodurile cu inaltimi intre $0$ si $2$ vor forma un interval, [{$3..5$}] alt interval si ultimul interval de inaltimi [{$6..8$}]). Astfel, pentru fiecare nod, pe langa tatal sau, vom retine si tatal din intervalul de mai sus, printr-o parcurede DF. In continuare, codul:
int i;
$H$ se calculeaza inainte sau poate fi constant
$T$ sunt tatii nodului si $N$ numarul de noduri
T2[n] = t2, Lev[n] = lev;
if (lev % H == 0) t2 = n;
for (i = 0; i < N; i++)
if (T[i] == n) DF(i, t2, lev+1);
}
p(pre).
{@void DF(int n, int t2, int lev)@}
{@{@}
{@ int i;@}
{@ T2[n] = t2, Lev[n] = lev;@}
{@ if (lev % H == 0) t2 = n;@}
{@ for (i = 0; i < N; i++)@}
{@ if (T[i] == n) DF(i, t2, lev+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:
