Se da un vector $A$ cu $N$ elemente naturale. Asupra lui se vor face $M$ operatii, codificate astfel in fisierul de intrare:
{*} 0 $a$ $b$ - Valorii elementului de pe pozitia $a$ ii se va adauga valoarea $b$.
{*} 1 $a$ $b$ - Sa se determine suma valorilor elementelor intervalului [a,b].

{*} 2 $a$ - Sa se determine pozitia $k$ astfel incat suma primilor k-termeni sa fie $a$.

{*} 2 $a$ - Sa se determine pozitia minima $k$ astfel incat suma valorilor primilor k-termeni sa fie exact $a$.

h2. Date de intrare

h2. Solutie

O rezolvare brute a problemei ar obtine in jur de 30 puncte si o poti gasi aici....

O rezolvare brute a problemei ar obtine in jur de 30 puncte si o poti gasi "aici":.

O alta solutie este una care are complexitatea pentru operatiile de tip $0$ si $1$, O({$logN$}), iar pentru operatia de tip $2$, O({$log^2^N$}).

O alta solutie este una care are pentru operatiile de tip $0$ si $1$, complexitatea O({$logN$}), iar pentru operatia de tip $2$, complexitatea O({$log^2^N$}) folosind o cautare binara. Aceasta solutie poate fi realizata prin intermediul "arborilor indexati binar":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees. Detalii privind aceasta solutie gasesti "aici":.

O rezolvare brute a problemei ar obtine in jur de 30 puncte si o poti gasi 'aici':job_detail/147500?action=view-source. Solutia optima pentru rezolvare a problemei are complexitate O({$MlogN$}) si se poate realiza in mai multe moduri.
Prima rezovare consta in folosirea 'arborilor de intervale':problema/arbint. O solutie care merge pe ideea aceasta gasesti 'aici':job_detail/147552.
A doua solutie se realizeaza intermediul 'arborilor indexati binar':problema/aib?action=download&file=aib.pdf, care foloseste mai putina memorie O(N). O solutie de 100 puncte pe ideea aceasta gasesti 'aici':job_detail/147499?action=view-source.
 
*Feedback Cosmin:* ar mai trebui adaugat un tip de query care este ignorat de obicei si e destul de util: gasirea elementului i astfel ca suma de a[j] 1 <= j <= i sa fie egala cu k. Aceasta operatie se poate implementa naiv cu cautare binara in O(log^2 n) dar te poti folosi de structura arborelui ca sa o faci in O(log n).
 
Baga si articolul asta http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees care  cred ca e ceva mai bun decat cel al lui Mihai.
 
Si baga si paperul original http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf
 
Mentioneaza ca se pot generaliza in mai multe dimensiuni, si ca de obicei daca ai k dimensiuni atunci ei folosesc max^k^ spatiu, dar daca folosesti un hash map vor folosi n * log^k^ max spatiu, unde max e coordonata maxima si n e numarul de querieuri/updateuri. Cred ca e explicat ceva despre chestia asta in articolul meu de cautari ortogonale.
 
Alta chestie de mentionat ar fi ca pe arbori indexati binar poti face queriuri de minm nu numai de suma, dar pe intervale 1..x nu x..y.

Solutia optima are complexitatea O({$logN$}) pentru fiecare operatie si se realizeaza tot prin intermediul arborilor indexati binar, folosindu-ne de structura acestora. Mai multe detalii privind implementare gasesti "aici":.

h2. Probleme similare