| 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 - 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.
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 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.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 150 000
- 1 ≤ Ai ≤ 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 ≤ 231
- Rezultatul pentru fiecare operatie se va incadra pe 32 de biti
Exemplu
| aib.in | aib.out |
|---|---|
| 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 |
Solutie
O rezolvare brute a problemei obtine in jur de 30 puncte si o poti gasi aici.
O alta solutie este una care are pentru operatiile de tip 0 si 1, complexitatea O(log2N), iar pentru operatia de tip 2, complexitatea O(log22N) folosind o cautare binara. Aceasta solutie poate fi realizata prin intermediul arborilor indexati binar, implementarea gasindu-se aici. De asemenea, un articol care trateaza foarte bine aceasta structura de date se gaseste in gazeta de informatica.
Solutia optima are complexitatea O(log2N) pentru fiecare operatie si se realizeaza tot prin intermediul arborilor indexati binar, folosindu-ne de structura acestora. Mai multe detalii privind implementare gasesti aici.
