Consultas de intervalo mais rápidas
Dado um array
a de n inteiros, pretende-se responder a q consultas. Todas as consultas têm a forma: “Qual é a soma dos elementos do array a entre os índices [l; r]?” (os dois extremos são inclusivos e a contagem começa em 0). Desta vez, tanto o número de consultas como o tamanho do array são substancialmente maiores. Consegue imaginar uma forma de obter essas respostas mais depressa?Input
A primeira linha da entrada contém um único inteiro
n – o número de elementos do array (1 ≤ n ≤ ).A linha seguinte contém
n inteiros, separados por espaço, que representam os elementos do array ().Output
O programa deve imprimir
q linhas; cada uma delas exibirá a soma dos elementos no array a entre os índices (incluindo ambos).Examples
Input | Output |
8
1 2 3 4 5 6 7 8
3
0 4
5 6
5 7 | 15
13
21 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 25 MB