Consultas de rango más rápidas
Dado un array
a de n enteros, necesitas responder q consultas. Todas las consultas tienen la forma: “¿Cuál es la suma de los elementos en el array a entre los índices [l; r]?” (ambos extremos son inclusivos y la indexación empieza en 0). En esta ocasión, tanto el número de consultas como el tamaño del array son considerablemente mayores. ¿Se te ocurre cómo responder esas consultas de manera más rápida?Entrada
La primera línea de la entrada contiene un único entero
n: la cantidad de elementos en el array (1 ≤ n ≤ ). La siguiente línea contiene n enteros separados por un espacio, que representan los elementos del array .La línea siguiente contiene un único entero
q, que indica el número de consultas (1 ≤ q ≤ ). Las siguientes q líneas contienen consultas de la forma .Salida
El programa debe imprimir
q líneas; cada una mostrará la suma de los elementos del array a entre los índices (ambos inclusivos).Ejemplos
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