Sommes sur les sous-segments
Problem
Implémentez une structure de données pour calculer efficacement les sommes d'éléments de tableau consécutifs.
Entrée
La première ligne contient un nombre naturel N (1 ≤ N ≤ 100000) — le nombre de nombres dans le tableau.
La deuxième ligne contient N nombres de 1 à 100000 — éléments de tableau.
La troisième ligne contient un nombre naturel K (1 ≤ K ≤ 30000) — le nombre de demandes pour calculer le montant.
Les K lignes suivantes contiennent deux nombres — les numéros des éléments gauche et droit du segment de tableau (on suppose que les éléments du tableau sont numérotés à partir de un)."
Mentions légales
Pour chaque requête, imprimez la somme des nombres de la section correspondante du tableau. Imprimez les chiffres sur une ligne séparés par un espace.
| Entrée |
Sortie |
5
4 4 8 7 8
2
1 2
1 3
| 8 16 |