Tabla de área sumada: suma de subarrays

Dada una array de tamaño M x N, hay un gran número de consultas para encontrar sumas de subarrays. Las entradas a las consultas son los índices superior izquierdo e inferior derecho de la subarray cuya suma es averiguar. 

Cómo preprocesar la array para que las consultas de suma de subarray 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 hacer un bucle de todas las consultas y calcular cada consulta en el peor de los casos O (q*(N*M)), que es demasiado grande para un amplio rango 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: 

Summed Area Table puede reducir este tipo de consulta a un tiempo de preprocesamiento de O(M*N) y cada consulta se ejecutará en O(1). Summed Area Table es una estructura de datos y un algoritmo para generar de manera rápida y eficiente la suma de valores en un subconjunto rectangular de una cuadrícula. 

El valor en cualquier punto (x, y) en la tabla de área sumada 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 Shubham Saxena contribuye con este artículo. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.