Module: Árbol de segmentos

Problem

Implemente una estructura de datos para calcular de manera eficiente las sumas de elementos de matriz consecutivos.

Entrada
La primera línea contiene un número natural N (1 ≤ N ≤ 100000) — el número de números en la matriz.

La segunda línea contiene N números del 1 al 100000 — elementos de matriz.

La tercera línea contiene un número natural K (1 ≤ K ≤ 30000) — el número de solicitudes para calcular la cantidad.

Las siguientes líneas K contienen dos números — los números de los elementos izquierdo y derecho del segmento de la matriz (se supone que los elementos de la matriz están numerados a partir de uno).'

Impresión
Para cada consulta imprima la suma de los números de la sección correspondiente de la matriz. Imprima los números en una línea separados por un espacio.
  Entrada Salida 5
4 4 8 7 8
2
1 2
1 3 8 16