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:job_detail/147552.
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.
