Range Sum Query
Vous obtenez 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 nums[left] + nums[left+1] + ... + nums[right], les deux extrémités étant incluses. Renvoyez 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 tout le tableau est égale à
18, celle des deux dernières valeurs à1 + 8 = 9, celle de l’index 0 seul à2, et celle des index 1 à 2 à7 + 1 = 8.
Pour aller plus loin
Si les nombres forment une grille et que chaque requête demande la somme d’un rectangle, comment étendrais-tu les sommes préfixes pour répondre à chaque requête en temps constant ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
De nombreuses requêtes portent sur presque les mêmes valeurs. Quel travail pourriez-vous faire une seule fois, avant de lire une requête ?
Si tu connaissais le total des
ipremières valeurs pour chaquei, une plage serait la différence entre deux de ces totaux.Construisez
prefixavecprefix[0] = 0etprefix[i+1] = prefix[i] + nums[i]. Ensuite, chaque requête[left, right]est égale àprefix[right+1] - prefix[left].
Solution
Une seule plage forme une boucle, mais chaque requête peut couvrir la majeure partie du tableau ; les additionner séparément répète donc les mêmes additions. Additionne une fois tout le tableau pour obtenir les sommes préfixes, et chaque plage se réduit alors à une seule soustraction.
Additionnez chaque plage
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Pour chaque requête, ajoutez nums[left] jusqu’à nums[right] à un total. C’est correct, car cela lit chaque valeur de l’intervalle, et c’est le mieux que vous puissiez faire pour une requête. Une requête peut couvrir jusqu’à n valeurs, donc q requêtes nécessitent jusqu’à n × q additions : 1.5 × 10^7 lorsque n = 10^4 et q = 1500, presque toutes répétées.
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 [3, -2, 5, 1, -4, 6], on obtient [0, 3, 1, 6, 7, 3, 9].
L’intervalle [left, right] correspond à la somme de tous les éléments jusqu’à l’indice right, moins celle de tous les éléments avant l’indice left : prefix[right+1] - prefix[left]. Pour [1, 4], cela donne prefix[5] - prefix[1] = 3 - 3 = 0. Le 0 initial permet d’utiliser la même formule pour un intervalle commençant à l’indice 0. Un seul parcours avec n additions construit le tableau, puis chaque requête ne nécessite qu’une soustraction.
Algorithme
- Créez
prefixde longueurn+1avecprefix[0] = 0. - Pour chaque
ide0àn-1, définissezprefix[i+1] = prefix[i] + nums[i]. - Pour chaque requête
[left, right], ajoutezprefix[right+1] - prefix[left]aux réponses. - Renvoyez 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
- Écrire
prefix[right] - prefix[left]. Avecprefix[0] = 0, cela exclutnums[right], donc la plage[3, 3]renvoie0au lieu de1. - Faire en sorte que
prefixait la même longueur quenums, de sorte queprefix[i]incluenums[i]. Une plage commençant à 0 nécessite alorsprefix[-1], qui est hors limites ; Python lit silencieusement la dernière entrée à la place. - Arrêter la boucle de force brute à
i < right. Les deux extrémités sont incluses, donc[3, 3]ne ferait la somme d’aucun élément. - En Lua et en R, où le comptage commence à 1, la requête indexée à partir de 0
[left, right]couvrenums[left+1]ànums[right+1], et les indices du préfixe sont décalés de la même façon.
Questions fréquentes3
Qu’est-ce qu’un tableau de sommes préfixes ?
Un tableau où chaque entrée est le 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].
Quelle est la complexité temporelle des requêtes de somme sur une plage 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.
Et si le tableau pouvait changer entre les requêtes ?
Un tableau de sommes 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 une mise à jour comme une somme sur un intervalle en O(log n).
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.
def sumRange(nums, queries):
# Écrivez le code iciTest #1
Test #2
Arguments
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Résultat attendu
[6, 0, 1]