== 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 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/147099?action=view-source. Solutia optima pentru rezolvare a problemei are complexitate O({$MlogN$}) si se poate realiza prin intermediul 'arborilor indexati binar':problema/aib?action=download&file=aib.pdf. O solutie de 100 puncte pe ideea aceasta gasesti 'aici':/job_detail/147101?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.
 
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.
 
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
* 'Datorii':problema/datorii

* 'Evantai':problema/evantai

== include(page="template/taskfooter" task_id="aib") ==

2978