== 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 elementelor intervalului [a,b]
{*} 1 $a$ $b$ - Valoarea elementului de pe pozitia $a$ va deveni $b$.

{*} 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$.

h2. Date de intrare

h2. Restrictii

* $1$ ≤ $N$, $M$ ≤ $100000$

'* $1$ ≤ $N$, $M$ ≤ $50.000$

* $0 ≤ A{~i~} ≤ 10^4^$ 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^4^$;

* Rezultatul se va incadra pe $32$ de biti

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|

h3. Explicatie

h2. Solutie

...

O rezolvare brute a problemei ar obtine in jur de 30 puncte si o poti gasi 'aici':. Solutia optima pentru rezolvare a problemei are complexitate O({$MlogN$}) si se poate realiza prin intermediul 'arborilor indexati binar':. O solutie de 100 puncte pe ideea aceasta gasesti 'aici':.
 
h2. Probleme similare
 
* 'Datorii':problema/datorii

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