Requêtes de somme sur un intervalle (Range Sum Queries) 2
On vous donne un tableau de
n éléments ainsi que q requêtes. Il existe deux types de requêtes :- Obtenir la somme d'un intervalle donné
- Mettre à jour l'élément du tableau à la position spécifiée
Votre tâche consiste à traiter ces requêtes de manière efficace.
Entrée
La première ligne de l'entrée contient deux entiers
n et q (1 ≤ n, q ≤ 100 000), qui correspondent respectivement au nombre d’éléments du tableau et au nombre de requêtes.La deuxième ligne contient
n entiers séparés par des espaces (), qui représentent les éléments initiaux du tableau.Les
q lignes suivantes décrivent chacune une requête :- Pour les requêtes de somme sur un intervalle : la ligne commence par le nombre
1, suivi de deux entiers et (). Ils indiquent l’intervalle d’indices[ $$l_i, r_i$$ ]dont il faut calculer la somme.
- Pour les requêtes de mise à jour : la ligne commence par le nombre
2, suivi de deux entiers et (). Ils indiquent la position de l’élément à mettre à jour et sa nouvelle valeur .
Sortie
Pour chaque requête de somme sur un intervalle, affichez la somme des valeurs de l’intervalle demandé, chacune sur sa propre ligne.
Exemples
Entrée | Sortie |
5 3
1 2 3 4 5
1 1 3
1 2 4
1 1 5 | 6
9
15 |
5 3
1 2 3 4 5
1 1 3
2 1 5
1 1 5 | 6
19 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB