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 - Valorii elementului de pe pozitia a ii 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 pentru acest tip, daca nu exista se va afisa -1.
Restrictii
- 1 ≤ M ≤ 100 000
- 1 ≤ M ≤ 150 000
- 1 ≤ Ai ≤ 10 000 pentru 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: 1 ≤ a ≤ 231
- Rezultatul 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 ar 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(logN), iar pentru operatia de tip 2, complexitatea O(log2N) folosind o cautare binara. Aceasta solutie poate fi realizata prin intermediul arborilor indexati binar. Detalii privind aceasta solutie gasesti aici.
Solutia optima are complexitatea O(logN) pentru fiecare operatie si se realizeaza tot prin intermediul arborilor indexati binar, folosindu-ne de structura acestora. Mai multe detalii privind implementare gasesti aici.
