Query su intervalli più veloci
Dato un array
a di n interi, dobbiamo rispondere a q interrogazioni. Tutte le interrogazioni chiedono: “Qual è la somma degli elementi dell’array a compresi tra gli indici [l; r]?” (entrambe le estremità sono incluse e l’indicizzazione inizia da 0). Questa volta la dimensione dell’array e il numero di interrogazioni sono molto più grandi. Riesci a trovare un modo per rispondere più velocemente a queste interrogazioni?Input
La prima riga di input contiene un singolo intero
n - il numero di elementi nell’array (1 ≤ n ≤ ). La riga successiva contiene n interi separati da uno spazio, che rappresentano gli elementi dell’array ().La riga seguente contiene un singolo intero
q - il numero di interrogazioni (1 ≤ q ≤ ). Le successive q righe contengono interrogazioni della forma .Output
Il programma deve stampare
q righe: ognuna dovrà contenere la somma degli elementi dell’array a compresi tra gli indici (entrambi inclusi).Esempi
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