Segment Tree (Albero di Segmenti)
TODO: spiegazione più dettagliata del segment tree
Un segment tree è una struttura dati basata su un albero binario che rappresenta un dato array o lista di elementi. Ogni nodo dell’albero corrisponde a un segmento o sottovettore dell’array originale.
Nel segment tree, il nodo radice rappresenta l’intero array, mentre i nodi foglia rappresentano i singoli elementi dell’array stesso. I nodi interni, invece, rappresentano segmenti ottenuti dividendo l’array in sottovettori più piccoli.
In genere, se un nodo rappresenta il sottovettore [l, r], il suo figlio sinistro rappresenterà il sottovettore [l, (l+r)/2], mentre il figlio destro rappresenterà [(l+r)/2 + 1, r]. Questa suddivisione ricorsiva continua finché ogni foglia non rappresenta un singolo elemento dell’array originale.
Il valore memorizzato in ciascun nodo del segment tree dipende dal tipo di problema o di query che si vuole risolvere. Spesso, i segment tree vengono impiegati per calcolare in modo efficiente valori aggregati su un intervallo, come somme, minimi, massimi o altre operazioni su sottovettori. Il valore di ciascun nodo è calcolato sulla base dei valori dei suoi nodi figli.
I segment tree sono particolarmente utili per risolvere problemi che richiedono query o aggiornamenti su intervalli in un array. Grazie alla loro struttura, è possibile eseguire queste operazioni in modo efficiente, con complessità O(log N), dove N è la dimensione dell’array originale.
In definitiva, il segment tree fornisce una struttura dati potente per gestire operazioni basate su intervalli in un array e permette di eseguire query e aggiornamenti di sottovettori in modo efficiente. Trova impiego in numerosi algoritmi e problemi che includono query su intervalli, aggiornamenti di range e molto altro.
Challenge: Iterative Segment Tree Node Calculation
Viene fornito un array di n elementi. Il tuo compito è costruire iterativamente un segment tree e calcolare il valore di ciascun nodo. Il valore di ogni nodo rappresenta la somma del sottovettore corrispondente.
Input
La prima riga di input contiene un intero n (1 ≤ n ≤ 100 000), che indica il numero di elementi dell’array.
La seconda riga contiene n interi separati da uno 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 separati 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