Range Sum Query
On vous donne un tableau d’entiers nums qui ne change jamais et une liste de queries. Chaque requête est une paire [left, right] d’indices commençant à 0, et demande le résultat de nums[left] + nums[left+1] + ... + nums[right], les deux extrémités incluses. Retournez les réponses dans le même ordre que les requêtes.
Fonction
- numsinteger-array
- le tableau d’entiers, identique pour chaque requête
- queriesinteger-2d-array
- les intervalles à additionner, chacun étant une paire [left, right] avec left ≤ right
- Renvoieinteger-array
- la somme de chaque plage, une par requête, dans l’ordre des requêtes
Contraintes
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthpour chaque requête[left, right]
Exemples
- Entrée
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- Sortie
- [6, 0, 1]
- Explication
- Les indices de 0 à 2 contiennent
3 + (-2) + 5 = 6. Les indices de 1 à 4 contiennent-2 + 5 + 1 + (-4) = 0. L’intervalle[3, 3]correspond à la valeur unique1.
- Entrée
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Sortie
- [18, 9, 2, 8]
- Explication
- La somme de l’ensemble du tableau est égale à
2 + 7 + 1 + 8 = 18, celle des deux dernières valeurs à1 + 8 = 9, celle de l’index 0 seul à2et celle des index 1 à 2 à7 + 1 = 8.
+14 tests cachés à la soumission
Pour aller plus loin
Maintenant, les nombres forment une grille, et chaque requête demande la somme d’un rectangle défini par deux coins. Comment étendrais-tu les sommes préfixes pour répondre à chaque requête en un nombre constant d’opérations ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
De nombreuses requêtes couvrent presque les mêmes valeurs. Quel travail pourriez-vous effectuer une seule fois, avant de lire la moindre requête ?
Si tu connaissais le total des
ipremières valeurs pour chaquei, une plage serait la différence entre deux de ces totaux.Construis
prefixavecprefix[0] = 0etprefix[i+1] = prefix[i] + nums[i]. Ensuite, chaque requête[left, right]estprefix[right+1] - prefix[left].
Solution
Une plage est une boucle. Le problème, c’est leur nombre : chaque requête peut couvrir la majeure partie du tableau, donc les additionner séparément répète sans cesse les mêmes additions. Additionne tout une seule fois dans des sommes préfixes, et chaque plage se réduit à une soustraction.
Additionnez chaque plage
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Réponds à chaque requête séparément : initialise un total à 0, additionne nums[left] jusqu’à nums[right], puis stocke le résultat. Pour [1, 4] dans [3, -2, 5, 1, -4, 6], cela donne -2 + 5 + 1 + (-4) = 0.
C’est correct, et pour une seule requête, c’est le mieux que tu puisses faire : tu dois lire chaque valeur de l’intervalle une fois. Le coût vient des répétitions. Une requête peut couvrir jusqu’à n valeurs ; q requêtes coûtent donc jusqu’à n × q additions. Avec n = 10^4 et 1500 requêtes couvrant chacune la majeure partie du tableau, cela représente environ 1.3 × 10^7 additions, dont presque toutes répètent un travail déjà effectué pour une requête précédente.
En plus de la liste des réponses, l’algorithme conserve un seul total ; l’espace supplémentaire est donc de O(1).
Algorithme
- Créez une liste de réponses vide.
- Pour chaque requête
[left, right], définisseztotal = 0. - Ajoutez
nums[i]àtotalpour chaqueideleftàright, bornes incluses. - Ajoutez
totalaux réponses et renvoyez-les après la dernière requête.
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answersSommes préfixes
Intuition
Soit prefix[i] la somme des i premières valeurs, avec prefix[0] = 0 pour le début vide. Pour [3, -2, 5, 1, -4, 6], on obtient prefix = [0, 3, 1, 6, 7, 3, 9]. Chaque entrée est égale à la précédente plus une valeur, donc le calcul du tableau entier nécessite n additions.
La plage [left, right] correspond à tout ce qui va jusqu’à l’indice right inclus, moins tout ce qui précède l’indice left. Cela donne prefix[right+1] - prefix[left]. Pour [1, 4] : prefix[5] - prefix[1] = 3 - 3 = 0. Pour [0, 2] : prefix[3] - prefix[0] = 6 - 0 = 6. Le 0 initial permet de traiter une plage commençant à l’indice 0 sans cas particulier.
La construction du tableau coûte O(n), et chaque requête ne coûte ensuite qu’une soustraction, soit un temps total de O(n + q) et un espace supplémentaire de O(n). Aucune somme préfixe ne dépasse 10^4 × 10^4 = 10^8, donc les entiers sur 32 bits suffisent.
Algorithme
- Crée un
prefixde longueurn+1avecprefix[0] = 0. - Pour chaque
ide0àn-1, définisprefix[i+1] = prefix[i] + nums[i]. - Pour chaque requête
[left, right], ajouteprefix[right+1] - prefix[left]aux réponses. - Retourne les réponses.
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
Pièges et cas limites
Presque tous les bogues ici sont dus à un indice décalé d’une unité.
- Écrire
prefix[right] - prefix[left]. Avecprefix[0] = 0, cela exclutnums[right], donc l’intervalle[3, 3]renvoie0au lieu de la valeur à l’indice 3. - Construire
prefixavec la même longueur quenums, de sorte queprefix[i]incluenums[i]. Alors, pour un intervalle qui commence à0, il faut utiliserprefix[left-1], qui est hors limites et, en Python, lit silencieusement la dernière entrée. Le0supplémentaire au début évite ce cas particulier. - Arrêter la force brute à
i < right. Les deux extrémités de l’intervalle sont incluses. - Oublier qu’en Lua et en R, le comptage commence à 1. La requête indexée à partir de 0
[left, right]couvrenums[left+1]ànums[right+1]dans ces langages, et la différence des préfixes est décalée de la même façon. - Utiliser un total sur 32 bits lorsque les valeurs ou les longueurs augmentent. Ici, la somme maximale est
10^8, mais avec des valeurs proches de10^9, une somme préfixe déborde rapidement ; un tableau sur 64 bits est donc le choix sûr par défaut.
Questions fréquentes4
Qu’est-ce qu’un tableau de sommes préfixes ?
C’est un tableau où chaque entrée correspond au total de toutes les valeurs précédant une position : prefix[i] = nums[0] + ... + nums[i-1], avec prefix[0] = 0. Tu le construis en un seul passage, puis la somme de n’importe quelle plage [left, right] est prefix[right+1] - prefix[left], une seule soustraction.
Quelle est la complexité temporelle des requêtes de somme sur un intervalle avec des sommes préfixes ?
O(n) pour construire le tableau des préfixes une seule fois, puis O(1) par requête, soit O(n + q) pour q requêtes. Additionner directement chaque intervalle coûte jusqu’à O(n) par requête, soit O(n·q) au total.
Pourquoi le tableau de préfixes a-t-il une entrée de plus que nums ?
Le prefix[0] = 0 supplémentaire représente le début vide du tableau. Avec lui, chaque plage utilise la même formule, y compris les plages qui commencent à l’index 0 : prefix[right+1] - prefix[0]. Sans lui, il faut une branche distincte pour left = 0.
Et si le tableau pouvait changer entre les requêtes ?
Un tableau de préfixes n’est donc pas le bon outil, car une mise à jour décale tous les totaux qui la suivent et coûte O(n) à corriger. Un arbre de Fenwick ou un arbre de segments gère à la fois une mise à jour et une somme sur un intervalle en O(log n). Lorsque le tableau ne change jamais, les simples sommes préfixes sont plus rapides et plus concises.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def sumRange(nums, queries):
# Écrivez le code iciCas 1
Cas 2
Entrée
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Attendu
[6, 0, 1]