Somme Alternée
On vous donne un tableau de
n entiers ainsi que q requêtes. Deux types de requêtes sont disponibles : mettre à jour l’élément du tableau à un indice p, et calculer la somme alternée d’une sous-partie du tableau [l; r].La somme alternée d’une sous-partie
[l; r] correspond à la somme des éléments placés aux indices pairs, à laquelle on soustrait la somme des éléments placés aux indices impairs de cette plage. Autrement dit, si la sous-partie [l; r] est composée des éléments , alors la somme alternée est donnée par .Pour chaque requête de type 2, vous devez calculer et afficher la somme alternée de la sous-partie
[l; r] correspondante.Entrée
La première ligne contient deux entiers
n et q, qui représentent la taille du tableau et le nombre de requêtes, respectivement (1 ≤ n, q ≤ ).Sortie
Pour chaque requête de type 2, affichez la somme alternée de la plage demandée dans une ligne distincte.
Exemples
Input | Output |
8 3
1 2 3 4 5 6 7 8
1 2 6
2 4 9
1 1 8 | 4
-9 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB