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 toate elementele 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:

== code(c) |B[st] += x;
B[dr + 1] -= x;

B[x2 + 1][y2 + 1] += v;
==

Pe cazul general, daca vrem sa facem operatii in $d$ dimensiuni vom avea o complexitate {$O(2^d^)$}. Reamintesc ca aceasta metoda este eficienta doar cand se vrea afisata vectorul/matricea/etc. doar la sfarsitul operatiilor, deoarece aflarea unui element este o operatie foarte ineficienta.

Pe cazul general, daca vrem sa facem operatii in $d$ dimensiuni vom avea o complexitate {$O(2^d^)$}. Reamintesc ca aceasta metoda este eficienta doar cand se vrea afisata vectorul/matricea/etc. doar la sfarsitul operatiilor sau sunt foarte putine interogari ale valorilor elementelor, deoarece aflarea unui element este o operatie foarte ineficienta: {$O(i)$} pentru a afla valorile elementelor pana la pozitia $i$.

h2. Grafuri cu liste de adiacenta (ideea originala de la Radu Berinde)