aib

Arbori indexati binar

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

Se da un vector 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$.

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

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 $0$, se va afisa pe cate o linie suma elementelor pentru intervalul cerut (in ordinea ceruta in fisierul de intrare).

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1$ ≤ $N$, $M$ ≤ $100000$
* $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^$;

h2. Exemplu