== 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$ 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$.
 

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 pentru acest tip, daca nu exista se va afisa -1.

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$

* 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$: $1$ ≤ $a$ ≤ $2^31^$

* Rezultatul se va incadra pe $32$ de biti
h2. Exemplu

h2. Solutie

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 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.