Dada una matriz de tamaño M x N, hay una gran cantidad de consultas para encontrar sumas de submatriz. Las entradas a las consultas son los índices superior izquierdo y inferior derecho de la submatriz cuya suma se debe averiguar. 

Cómo preprocesar la matriz para que las consultas de suma de submatriz se puedan realizar en tiempo O(1). 

Ejemplo:

  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)

Algoritmo ingenuo:  

Podemos repetir todas las consultas y calcular cada consulta en el peor de los casos O (q*(N*M)), que es demasiado grande para un rango grande de números.

// 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) 

Solución optimizada: 

Tabla de áreas sumadas Puede reducir este tipo de consulta a un tiempo de preprocesamiento de O (M*N) y cada consulta se ejecutará en O (1). La tabla de áreas sumadas es una estructura de datos y un algoritmo para generar rápida y eficientemente la suma de valores en un subconjunto rectangular de una cuadrícula. 

El valor en cualquier punto (x y) en la tabla de áreas sumadas es solo la suma de todos los valores arriba y a la izquierda de (x y) inclusive:

La solución optimizada se implementa en la siguiente publicación.

  Implementación de un enfoque optimizado.