1854 - Arbore Binar Complet

Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului sunt ocupate în întregime. În general, deși nu este obligatoriu, toate nodurile de pe ultimul nivel sunt grupate în partea stânga a acestuia.
Înălțimea unui arbore binare complet este [log2n]+1, unde n este numărul de noduri.

Pentru reprezentarea unui arbore binar complet se poate folosi un tablou unidimensional A cu n elemente, în felul următor:

• rădăcinii arborelui îi corespunde elementul A[1];
• dacă unui nod îi corespunde elementul A[k], descendentului stâng îi va corespunde elementul A[2*k], iar celui drept îi va corespunde elementul A[2*k+1].

Observăm că pentru un nod A[k], nodul părinte este A[k/2], unde k/2 este câtul împărțirii, fără zecimale.

Într-un arbore reprezentat astfel, nodurile de pe ultimul nivel sunt grupate în stânga. Dacă nodurile nu sunt grupate în stânga, sunt necesare câteva elemente în plus în vector, iar unele dintre ele nu vor fi folosite – nu vor avea un nod corespunzător.

Cerința

Se dau n numere naturale, reprezentând în ordine valorile nodurilor dintr-un arbore binar complet și m operații de tip 1 sau 2, aplicate unui nod k.

Operația de tip 1 determină valoarea nodului părinte a lui k, iar operația de tip 2 determină suma valorilor fiilor nodului k. Dacă k=1 sau dacă nodul k nu are fii, rezultatul va fi 0.

Afișați pentru fiecare operație rezultatul ei.

Date de intrare

Fișierul de intrare completin.txt conține pe prima linie numărul n, pe linia a doua n numere naturale, pe linia a treia m, iar pe următoarele m linii câte o pereche op k

Date de ieșire

Fișierul de ieșire completout.txt va conține rezultatele celor m operații, în ordine, câte unul pe linie.

Restricții și precizări

• 1 ≤ n ≤ 100000
• cele n numere citite vor fi mai mici decât 1.000.000
• 1 ≤ m ≤ 100000
• 1 ≤ op ≤ 2
• 1 ≤ k ≤ n

Exemplul 1

completin.txt

12

15 5 18 35 32 23 12 43 29 25 22 13

8

2 9

1 7

2 5

1 8

1 1

2 6

1 9

2 4

completout.txt

0

18

47

35

0

13

35

72

Exemplul 2

completin.txt

8

4 8 2 6 7 1 9 3

6

1 5

2 6

1 4

2 1

1 3

2 8

completout.txt

5

0

12

12

2

0

Rezolvare

<syntaxhighlight lang="python" line>

1. 1854 - Arbore Binar Complet

def parent(k):

   return k // 2 if k != 1 else 0

def children_sum(k):

   left_child = 2 * k
   right_child = 2 * k + 1
   left_value = values[left_child] if left_child <= n else 0
   right_value = values[right_child] if right_child <= n else 0
   return left_value + right_value

1. Verificare restricții

if not (1 <= n <= 100000 and all(1 <= value < 1000000 for value in values) and 1 <= m <= 100000 and all(1 <= op <= 2 and 1 <= k <= n for op, k in queries)):

   with open("completout.txt", "w") as fout:
       fout.write("Fals\n")

else:

   # Executarea operațiilor și scrierea rezultatelor în fișierul de ieșire
   with open("completout.txt", "w") as fout:
       for query in queries:
           op, k = query
           if op == 1:
               # Operația 1: valoarea nodului părinte al lui k
               fout.write(f"{values[parent(k)]}\n")
           elif op == 2:
               # Operația 2: suma valorilor fiilor nodului k
               fout.write(f"{children_sum(k)}\n")

</syntaxhighlight>