Somme préfixe
Les sommes préfixes sont très utiles lorsqu’on travaille avec des intervalles dans les tableaux. Il est souvent possible d’optimiser un programme en tirant parti de la somme préfixe d’un tableau, plutôt que de recalculer la somme à chaque fois.
Imaginons un problème où nous devons répondre à un grand nombre de requêtes (par exemple, des millions) du type « Quelle est la somme des éléments du tableau
a depuis le début jusqu’à ? ». Avec une approche naïve, nous calculerions à chaque fois la somme a[0] + a[1] + a[2] + ... + a[].a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # queriesNous pourrions lancer une boucle
for pour additionner a[0] + a[1] + a[2] + ... + a[] pour chaque requête, ce qui entraîne beaucoup d’opérations répétitives :res1 = a[0] + a[1] + a[2] + a[3]
res2 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
res3 = a[0] + a[1] + a[2]
res4 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]On remarque que la première partie des calculs est toujours la même. Avant de calculer
res2, nous connaissons déjà le résultat de a[0] + a[1] + a[2] + a[3], qui est exactement res1. Avant de calculer res4, nous connaissons déjà le résultat de a[0] + a[1] + a[2] + a[3] + a[4] + a[5]. Nous pouvons donc optimiser ces calculs et répondre aux requêtes instantanément, au lieu de lancer une boucle for à chaque fois.Pour cela, nous allons créer un nouveau tableau
p de sommes préfixes. Les éléments de p représenteront la somme des éléments du tableau a jusqu’à l’indice correspondant. Grâce à ce tableau de sommes préfixes, la réponse à chaque requête se résumera à accéder directement à un élément de p :p[0] = a[0]
p[1] = a[0] + a[1]
p[2] = a[0] + a[1] + a[2]
p[3] = a[0] + a[1] + a[2] + a[3]
p[4] = a[0] + a[1] + a[2] + a[3] + a[4]
p[5] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
p[6] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
p[7] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]On voit un schéma récurrent : pour calculer l’élément suivant dans
p, on reprend le résultat précédent et on y ajoute le nouvel élément de a. Ainsi, nous réutilisons les calculs déjà effectués sans avoir besoin de tout additionner de nouveau :p[0] = a[0]
p[1] = p[0] + a[1]
p[2] = p[1] + a[2]
p[3] = p[2] + a[3]
p[4] = p[3] + a[4]
p[5] = p[4] + a[5]
p[6] = p[5] + a[6]
p[7] = p[6] + a[7]Ce tableau de sommes préfixes peut être calculé en une seule boucle
for de complexité linéaire, plutôt que via de multiples additions répétées. Une fois le tableau p obtenu, toutes les requêtes sont traitées instantanément : p[i] contient déjà la somme a[0] + a[1] + a[2] + ... + a[i]. Ainsi, pour chaque requête , la réponse sera simplement p[].Pouvez-vous calculer le tableau de sommes préfixes maintenant ?
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ). La deuxième ligne contient n entiers séparés par des espaces, représentant le tableau a .Sortie
Le programme doit afficher le tableau des sommes préfixes de
a.Exemples
Entrée | Sortie |
8
8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 20 MB