Consultas de Soma em Intervalos
É-lhe dado um array de
n elementos e q queries de soma em intervalo. O seu objetivo é responder de forma eficiente a cada query, calculando a soma dos elementos num intervalo específico, utilizando uma árvore de segmentos (segment tree).Entrada
A primeira linha da entrada contém dois inteiros
n e q (1 ≤ n, q ≤ 100 000), que representam o número de elementos do array e o número de queries, respetivamente.A segunda linha contém
n inteiros separados por espaços, (), correspondentes aos elementos do array.As
q linhas seguintes contêm cada uma dois inteiros e (), que indicam o intervalo de cada query.Saída
Para cada query, imprima a soma dos elementos no intervalo indicado em linhas separadas.
Exemplos
Entrada | Saída |
5 3
1 2 3 4 5
1 3
2 4
1 5 | 6
9
15 |
Explicação
Para o array
[1, 2, 3, 4, 5], efetuam-se as seguintes queries de soma em intervalo:- Query
[1, 3]: A soma dos elementos no intervalo [1, 3] é 1 + 2 + 3 = 6.
- Query
[2, 4]: A soma dos elementos no intervalo [2, 4] é 2 + 3 + 4 = 9.
- Query
[1, 5]: A soma dos elementos no intervalo [1, 5] é 1 + 2 + 3 + 4 + 5 = 15.
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB