Supongamos que tenemos un arreglo llamado A.
Un subarreglo de A está definido como cualquier bloque de elementos consecutivos en A. Por ejemplo, si A = [5, -2, 1, 4], entonces A tiene 10 subarreglos que son:
[5][5, -2][5, -2, 1][5, -2, 1, 4][-2][-2, 1][-2, 1, 4][1][1, 4][4].Por otro lado, [5, -2, 4] no es un subarreglo de A porque estos elementos no aparecen de forma consecutiva en A.
Una manera de describir un subarreglo es usando dos índices de A que describen dónde empieza y dónde termina el subarreglo. Llamemos p al índice izquierdo y q al índice derecho. Por ejemplo:
[5, -2] se describe con p = 0 y q = 1;[-2, 1, 4] se describe con p = 1 y q = 3;[1] se describe con p = 2 y q = 2;[5, -2, 1, 4] se describe con p = 0 y q = 3.Escribe un programa que recibe varias "consultas" de la forma p, q y para cada consulta calcula la suma de todos los elementos del subarreglo que empieza en p y termina en q.
La entrada contiene varias líneas:
N, el número de elementos en el arreglo.N enteros Ai para 0 ≤ i < N, los elementos del arreglo. Estos números están separados por espacios. Está garantizado que Ai satisface -104 ≤ Ai ≤ 104.C, el número de consultas.C líneas, cada una con un consulta descrita por dos índices p y q separados por un espacio. Está garantizado que 0 ≤ p ≤ q < N (es decir, p y q son índices válidos).La salida debe tener exactamente C líneas (una por consulta).
Para cada consulta, escribe una línea con la suma de los elementos del subarreglo que empieza en p y termina en q.
4
5 -2 1 4
4
0 1
1 3
2 2
0 3
3
3
1
8
La entrada nos da un arreglo A = [5, -2, 1, 4] y 4 consultas:
0 1) corresponde al subarreglo [5 -2]. La suma de estos elementos es 3.1 3) corresponde al subarreglo [-2 1 4]. La suma de estos elementos también es 3 (por casualidad).2 2) corresponde al subarreglo [1]. La suma de este único elemento es 1.0 3) corresponde al arreglo completo, [5 -2 1 4]. La suma de estos elementos es 8.1 ≤ N ≤ 100 y 1 ≤ C ≤ 100.1 ≤ N ≤ 50,000 y 1 ≤ C ≤ 50,000.