Дадена е матрица с размер M x N, има голям брой заявки за намиране на суми на подматрици. Входове към заявките са левият горен и десен долен индекси на подматрицата, чиято сума трябва да се намери. 

Как да обработим предварително матрицата, така че заявките за суми на подматрици да могат да се изпълняват за O(1) време. 

Пример:

  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)

Наивен алгоритъм:  

Можем да завъртим всички заявки и да изчислим всяка заявка в най-лошия случай O (q*(N*M)), което е твърде голямо за голям диапазон от числа.

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

Оптимизирано решение: 

Таблица със сумирана площ може да намали този тип заявка до време за предварителна обработка от O(M*N) и всяка заявка ще се изпълни в O(1). Таблицата със сумирана площ е структура от данни и алгоритъм за бързо и ефективно генериране на сумата от стойности в правоъгълно подмножество на мрежа. 

Стойността в която и да е точка (x y) в таблицата със сумирани области е само сумата от всички стойности отгоре и отляво на (x y) включително:

Оптимизираното решение е внедрено в публикацията по-долу.

  Прилагане на оптимизиран подход