Somme préfixe 2D (2D prefix sum)
Étant donné un grand tableau 2D de nombres comportant
r lignes et c colonnes, l’objectif est de calculer la somme préfixe 2D (2D prefix sum) de ce tableau. La valeur de la somme préfixe 2D à une position (r, c) correspond à la somme de tous les éléments compris entre le coin (0, 0) et l’élément (r, c). Autrement dit, c’est la somme des éléments de la sous-matrice dont les coins sont (0, 0), (r, 0), (r, c) et (0, c).Pouvez-vous déterminer efficacement la somme préfixe 2D pour tous les emplacements de la matrice ?
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
Entrée
La première ligne de l’entrée contient deux entiers - le nombre de lignes du tableau
r et le nombre de colonnes c (1 ≤ r, c ≤ 1000).Les
r lignes suivantes contiennent chacune c entiers séparés par un espace, représentant les éléments de la matrice .Sortie
Le programme doit afficher
r lignes contenant c nombres, qui représentent la matrice de la somme préfixe 2D.Exemples
Input | Output |
3 5
1 2 -3 4 6
-1 3 8 4 0
0 1 -2 0 5 | 1 3 0 4 10
0 5 10 18 24
0 6 9 17 28 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 15 MB