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.

Arborele binar de mai jos este complet:

Înălțimea unui arbore binare complet este , unde  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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

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

0
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

Datele nu corespund restrictiilor impuse

Rezolvare

def verifica_restrictii(n, m, operatii, arb):
    if not (1 <= n <= 100000):
        return False
    if not all(0 <= num < 1000000 for num in arb[1:]):  # index 0 este ignorat
        return False
    if not (1 <= m <= 100000):
        return False
    if not all(1 <= op <= 2 and 1 <= k <= n for op, k in operatii):
        return False
    return True

def main():
    with open("completIN.txt", "r") as fin:
        n = int(fin.readline().strip())
        arb = [0] + list(map(int, fin.readline().strip().split()))
        m = int(fin.readline().strip())
        operatii = [tuple(map(int, fin.readline().strip().split())) for _ in range(m)]

    if not verifica_restrictii(n, m, operatii, arb):
        with open("completOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return

    with open("completOUT.txt", "w") as fout:
        for op, k in operatii:
            if op == 1:
                if k == 1:
                    fout.write("0\n")
                else:
                    fout.write(f"{arb[k//2]}\n")

            elif op == 2:
                if k*2 > n and k*2+1 > n:
                    fout.write("0\n")
                elif k*2 <= n and k*2+1 > n:
                    fout.write(f"{arb[k*2]}\n")
                elif k*2 <= n and k*2+1 <= n:
                    fout.write(f"{arb[k*2] + arb[k*2+1]}\n")

if __name__ == "__main__":
    main()