Somme su sottosegmenti
Problem
Implementa una struttura dati per calcolare in modo efficiente le somme di elementi consecutivi dell'array.
Inserimento
La prima riga contiene un numero naturale N (1 ≤ N ≤ 100000) — il numero di numeri nell'array.
La seconda riga contiene N numeri da 1 a 100000 — elementi dell'array.
La terza riga contiene un numero naturale K (1 ≤ K ≤ 30000) — il numero di richieste per calcolare l'importo.
Le successive righe K contengono due numeri — i numeri degli elementi sinistro e destro del segmento dell'array (si presuppone che gli elementi dell'array siano numerati a partire da uno).'
Impressum
Per ogni interrogazione stampa la somma dei numeri della corrispondente sezione dell'array. Stampa i numeri su una riga separati da uno spazio.
| Input |
Uscita |
5
4 4 8 7 8
2
1 2
1 3
| 8 16 |