Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | aib.in, aib.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Bondane Cosmin •cos_min |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Arbori indexati binar
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.
Date de intrare
Pe prima linie a fisierului de intrare se afla N si M. Pe urmatoarea linie se gasesc cele N elemente ale vectorului, iar urmatoarele M linii descriu operatia care trebuie efectuata.
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).
Restrictii
- 1 ≤ N, M ≤ 50 000
- 1 ≤ Ai ≤ 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
Exemplu
| 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 |
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 in mai multe moduri.
Prima rezovare consta in folosirea arborilor de intervale. O solutie care merge pe ideea aceasta gasesti aici.
A doua solutie se realizeaza intermediul arborilor indexati binar, care foloseste mai putina memorie O(N). O solutie de 100 puncte pe ideea aceasta gasesti aici.
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).
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 maxk spatiu, dar daca folosesti un hash map vor folosi n * logk 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.
