Des requêtes sur des intervalles plus rapides
Étant donné un tableau
a de n entiers, vous devez traiter q requêtes. Toutes les requêtes sont de la forme : « Quelle est la somme des éléments du tableau a entre les indices [l; r] ? » (les deux bornes sont inclusives et l’indexation commence à 0). Cette fois, la taille du tableau et le nombre de requêtes sont bien plus importants. Pouvez-vous trouver un moyen de répondre à ces requêtes plus rapidement ?Entrée
La première ligne de l’entrée contient un entier
n, qui indique le nombre d’éléments dans le tableau (1 ≤ n ≤ ). La ligne suivante contient n entiers séparés par des espaces, représentant les éléments du tableau .La ligne suivante contient un entier
q - le nombre de requêtes (1 ≤ q ≤ ). Les q lignes qui suivent contiennent chacune une requête sous la forme .Sortie
Le programme doit afficher
q lignes, chacune contenant la somme des éléments du tableau a entre les indices (inclusivement).Exemples
Entrée | Sortie |
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