Étant donné une matrice de taille M x N, il existe un grand nombre de requêtes pour trouver les sommes des sous-matrices. Les entrées des requêtes sont les index en haut à gauche et en bas à droite de la sous-matrice dont la somme est à découvrir. 

Comment prétraiter la matrice afin que les requêtes de somme de sous-matrice puissent être effectuées en un temps O(1). 

Exemple:

  tli :   Row number of top left of query submatrix   tlj :   Column number of top left of query submatrix   rbi :   Row number of bottom right of query submatrix   rbj :   Column number of bottom right of query submatrix Input: mat[M][N] = {{1 2 3 4 6} {5 3 8 1 2} {4 6 7 5 5} {2 4 8 9 4} }; Query1: tli = 0 tlj = 0 rbi = 1 rbj = 1 Query2: tli = 2 tlj = 2 rbi = 3 rbj = 4 Query3: tli = 1 tlj = 2 rbi = 3 rbj = 3; Output: Query1: 11 // Sum between (0 0) and (1 1) Query2: 38 // Sum between (2 2) and (3 4) Query3: 38 // Sum between (1 2) and (3 3)

Algorithme naïf :  

Nous pouvons boucler toutes les requêtes et calculer chaque requête dans le pire des cas O (q*(N*M)) qui est trop grand pour une large plage de nombres.

// Pseudo code of Naive algorithm. Arr[][] = input_matrix For each query: Input tli tlj rbi rbj sum = 0 for i from tli to tbi (inclusive): for j from tlj to rbj(inclusive): sum += Arr[i][j] print(sum) 

Solution optimisée : 

Tableau des superficies additionnées peut réduire ce type de requête en un temps de prétraitement de O(M*N) et chaque requête s'exécutera en O(1). Summed Area Table est une structure de données et un algorithme permettant de générer rapidement et efficacement la somme des valeurs dans un sous-ensemble rectangulaire d'une grille. 

La valeur en tout point (x y) dans le tableau des aires additionnées est simplement la somme de toutes les valeurs au-dessus et à gauche de (x y) inclus :

La solution optimisée est implémentée dans l’article ci-dessous.

  Mise en œuvre d’une approche optimisée