== include(page="template/taskheader" task_id="aib") ==
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$ - Sa se determine suma valorilor elementelor intervalului [a,b].
{*} 1 $a$ $b$ - Valorii elementului de pe pozitia $a$ ii se va adauga valoarea $b$.

{*} 0 $a$ $b$ - Valorii elementului de pe pozitia $a$ i se va adauga valoarea $b$.
{*} 1 $a$ $b$ - Sa se determine suma valorilor elementelor intervalului {$[a,b]$}.
{*} 2 $a$ - Sa se determine pozitia minima $k$ astfel incat suma valorilor primilor $k$ termeni sa fie exact $a$.

h2. Date de intrare

h2. Date de iesire

Pentru fiecare operatie de tip $0$, se va afisa pe cate o linie suma valorilor elementelor pentru intervalul cerut (in ordinea ceruta in fisierul de intrare).

Pentru fiecare operatie de tip $1$ se va afisa pe cate o linie suma valorilor elementelor pentru intervalul cerut (in ordinea ceruta in fisierul de intrare), iar pentru fiecare operatie de tip $2$ se va afisa pozitia $k$ ceruta. Daca nu exista o astfel de pozitie se va afisa {$-1$} pentru operatia respectiva.
Va sfatuim sa cititi cu scanf si nu cu cin pentru o mai rapida citire a datelor de intrare.

h2. Restrictii

* $1$ ≤ $N$, $M$ ≤ $50 000$
* $1$ ≤ $A{~i~}$ ≤ $10 000$ pentru $1$ ≤ i ≤ $N$
* Pentru operatia de tip $0$: $1$ ≤ $a$ ≤ $b$ ≤ $N$
* Pentru operatia de tip $1$: $1$ ≤ $a$ ≤ $N$ si $1$ ≤ $b$ ≤ $10 000$
* Rezultatul se va incadra pe $32$ de biti

* $1 ≤ $N$ ≤ 100 000$
* $1 ≤ $M$ ≤ 150 000$
* $1 ≤ A{~i~} ≤ 10 000$, pentru orice {$i$}, $1 ≤ i ≤ N$
* Pentru operatia de tip $0$: $1 ≤ a ≤ N$ si $1 ≤ b ≤ 10 000$
* Pentru operatia de tip $1$: $1 ≤ a ≤ b ≤ N$
* Pentru operatia de tip $2$: $0 ≤ a ≤ 2^31^$
* Rezultatul pentru fiecare operatie se va incadra pe $32$ de biti

h2. Exemplu
table(example). |_. aib.in |_. aib.out |

| 6 5
3 8 4 7 8 8
0 1 5
0 6 6
1 4 4
1 2 9
1 1 9
| 30

| 8 6
25 42 8 15 1 55 16 67
0 5 12
2 25
2 90
1 7 7
1 2 8
2 241
| 1
4
16
216

8
|
h2. Solutie

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.

O rezolvare brute a problemei obtine in jur de $30$ puncte si o poti gasi 'aici':job_detail/170677?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).

O alta solutie este una care are pentru operatiile de tip $0$ si $1$, complexitatea {$O(log{~2~}N)$}, iar pentru operatia de tip $2$, complexitatea {$O(log{~2~}^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, implementarea gasindu-se 'aici':job_detail/170676?action=view-source. De asemenea, un articol care trateaza foarte bine aceasta structura de date se gaseste in 'gazeta de informatica':http://www.ginfo.ro/revista/13_1/focus.pdf.

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.

Solutia optima are complexitatea {$O(log{~2~}N)$} pentru fiecare operatie si se realizeaza tot prin intermediul arborilor indexati binar, folosindu-ne de structura acestora. Mai multe detalii privind implementare gasesti 'aici':job_detail/170675?action=view-source.

h2. Probleme similare

* 'Evantai':problema/evantai
== include(page="template/taskfooter" task_id="aib") ==

2978