Segment Tree (Albero dei segmenti) Ricorsivo
Ti viene fornito un array di
n elementi. Il tuo compito è costruire ricorsivamente un Segment Tree (albero dei segmenti) e calcolare il valore di ciascun nodo. Il valore di ogni nodo corrisponde alla somma del sottoarray che esso rappresenta.Input
La prima riga dell’input contiene un intero
n (1 ≤ n ≤ 100 000), che indica il numero di elementi nell’array.La seconda riga contiene
n interi separati da spazio (), che rappresentano gli elementi dell’array.Output
Stampa il Segment Tree con tutti i valori dei nodi. Ogni livello del Segment Tree deve essere stampato su una riga separata, con i valori divisi da uno spazio.
Esempi
Input | Output |
4
1 2 3 4 | 10
3 7
1 2 3 4 |
8
3 7 9 6 2 1 5 4 | 37
25 12
10 15 3 9
3 7 9 6 2 1 5 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 10 MB