== 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.
Alta chestie de mentionat ar fi ca pe arbori indexati binar poti face queriuri de minm nu numai de suma, dar pe intervale 1..x nu x..y.
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
