Segment Tree (árvore de segmentos)
TODO: more detailed segtree explanation
Uma Segment Tree (árvore de segmentos) é uma estrutura de dados baseada em árvore binária que representa um array ou lista de elementos. Cada nó da árvore corresponde a um segmento ou subarray do array original.
Na Segment Tree, o nó raiz representa todo o array, e os nós folha representam elementos individuais desse array. Os nós internos representam segmentos obtidos ao dividir o array em subarrays menores.
Normalmente, se um nó representa o subarray [l, r], o seu filho esquerdo representa [l, (l+r)/2] e o seu filho direito representa [(l+r)/2 + 1, r]. Este processo recursivo continua até que cada nó folha represente apenas um elemento do array original.
O valor armazenado em cada nó da Segment Tree depende do tipo de problema ou consulta que se pretende resolver. Geralmente, essa estrutura é usada para calcular valores agregados, como somas, mínimos, máximos ou outras operações em um subarray determinado. O valor de cada nó é calculado com base nos valores dos seus nós filhos.
As Segment Trees são particularmente úteis para lidar com problemas que envolvem consultas ou atualizações em intervalos de um array. Ao construir essa estrutura, podemos realizar operações de consulta e atualização de forma eficiente, com complexidade de O(log N), onde N é o tamanho do array.
No geral, a Segment Tree oferece uma solução poderosa para operações que envolvem intervalos em arrays, tornando rápidas tanto as consultas quanto as atualizações nesses segmentos. Ela é utilizada em várias aplicações e algoritmos, incluindo consultas por intervalo, atualizações em intervalos e muito mais.
Challenge: Iterative Segment Tree Node Calculation
Você tem um array de
n elementos. O seu objetivo é construir iterativamente uma Segment Tree e calcular o valor de cada nó na árvore. O valor de cada nó representa a soma do subarray correspondente.Entrada
A primeira linha da entrada contém um inteiro
n (1 ≤ n ≤ 100 000), que representa o número de elementos do array.A segunda linha contém
n inteiros separados por espaço (), que são os elementos do array.Saída
Imprima a Segment Tree com todos os valores de seus nós. Cada nível da árvore deve ser impresso em uma linha separada, com os valores separados por espaço.
Exemplos
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