Requêtes de somme sur intervalle
Vous disposez d’un tableau de
n éléments et de q requêtes de somme sur des intervalles. Votre objectif est de répondre efficacement à chacune de ces requêtes en calculant la somme des éléments dans l’intervalle spécifié, en utilisant une structure de données appelée arbre segmentaire (segment tree).Entrée
La première ligne de l’entrée contient deux entiers
n et q (1 ≤ n, q ≤ 100 000), qui indiquent respectivement le nombre d’éléments du tableau et le nombre de requêtes.La deuxième ligne contient
n entiers séparés par des espaces (), représentant les éléments du tableau.Les
q lignes suivantes contiennent chacune deux entiers et (), qui représentent la plage d’indices pour chaque requête.Sortie
Pour chaque requête, affichez la somme des éléments compris dans l’intervalle demandé, sur des lignes séparées.
Exemples
Entrée | Sortie |
5 3
1 2 3 4 5
1 3
2 4
1 5 | 6
9
15 |
Explication
Pour le tableau
[1, 2, 3, 4, 5], nous réalisons les requêtes de somme sur les intervalles suivants :- Requête
[1, 3]: la somme des éléments de l’intervalle [1, 3] est 1 + 2 + 3 = 6.
- Requête
[2, 4]: la somme des éléments de l’intervalle [2, 4] est 2 + 3 + 4 = 9.
- Requête
[1, 5]: la somme des éléments de l’intervalle [1, 5] est 1 + 2 + 3 + 4 + 5 = 15.
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB