Requête de Somme Préfixe
On vous donne un tableau de
n entiers positifs. Votre tâche consiste à traiter q requêtes, chacune pouvant être de deux types :- Vérifier s’il existe un sous-tableau préfixe du tableau dont la somme est égale à une valeur donnée
s.
- Mettre à jour la valeur à un indice précis du tableau.
Écrivez un programme pour répondre efficacement à ces requêtes.
Entrée
La première ligne contient deux entiers
n et q (1 ≤ n, q ≤ 100 000), séparés par un espace, indiquant la taille du tableau et le nombre de requêtes respectivement.La deuxième ligne contient
n entiers positifs, représentant les éléments du tableau. Chaque élément est positif et ne dépasse pas .Les
q lignes suivantes décrivent les requêtes. Chaque requête comporte un type (1 ou 2), suivi des paramètres adéquats :- Pour une requête de type 1 : un entier
s.
- Pour une requête de type 2 : une position
pet une valeurxà mettre à jour à cet indice.
Sortie
Pour chaque requête de type 1, affichez
YES s’il existe un sous-tableau préfixe dont la somme est égale à s, sinon affichez NO.Exemples
Entrée | Sortie |
5 3
1 2 3 4 5
1 10
2 2 3
1 15 | YES
NO |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB