Somas em subsegmentos
Problem
Implemente uma estrutura de dados para calcular eficientemente as somas de elementos consecutivos do array.
Entrada
A primeira linha contém um número natural N (1 ≤ N ≤ 100000) — o número de números na matriz.
A segunda linha contém N números de 1 a 100000 — elementos do array.
A terceira linha contém um número natural K (1 ≤ K ≤ 30000) — o número de solicitações para calcular o valor.
As próximas K linhas contêm dois números — os números dos elementos esquerdo e direito do segmento da matriz (presume-se que os elementos da matriz sejam numerados a partir de um).'
Impressão
Para cada consulta, imprima a soma dos números da seção correspondente da matriz. Imprima os números em uma linha separada por um espaço.
| Entrada |
Saída |
5
4 4 8 7 8
2
1 2
1 3
| 8 16 |