Dada uma matriz de tamanho M x N, há um grande número de consultas para encontrar somas de submatrizes. As entradas para as consultas são os índices superior esquerdo e inferior direito da submatriz cuja soma é descobrir. 

Como pré-processar a matriz para que as consultas de soma de submatrizes possam ser realizadas em tempo O(1). 

Exemplo:

  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 Ingênuo:  

Podemos fazer um loop em todas as consultas e calcular cada consulta no pior caso O (q*(N*M)), que é muito grande para um grande intervalo 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) 

Solução otimizada: 

Tabela de área somada pode reduzir esse tipo de consulta em um tempo de pré-processamento de O(M*N) e cada consulta será executada em O(1). Summed Area Table é uma estrutura de dados e algoritmo para gerar de forma rápida e eficiente a soma de valores em um subconjunto retangular de uma grade. 

O valor em qualquer ponto (x y) na tabela de áreas somadas é apenas a soma de todos os valores acima e à esquerda de (x y) inclusive:

A solução otimizada é implementada na postagem abaixo.

  Implementação de abordagem otimizada