Для матриці розміром 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) включно:

Оптимізоване рішення реалізовано в публікації нижче.

  Реалізація оптимізованого підходу