Суммируем любой прямоугольник за один шаг

Урок 24 давал сумму любого отрезка обычного списка одним вычитанием. Для этого заранее считались префиксные (накопленные) суммы. С сетками возникает тот же вопрос, только в двух измерениях. Дана сетка чисел. Какова сумма внутри прямоугольника: блока пикселей, диапазона ячеек таблицы, участка тепловой карты? Медленный способ складывает каждую ячейку прямоугольника, это O(rows × cols) на запрос (rows строк, cols столбцов). При тысячах запросов это безнадёжно. Двумерная префиксная сумма строит таблицу один раз. Потом она отвечает на любой прямоугольник любого размера четырьмя чтениями из таблицы.

Возьми сетку [[1,2,3],[4,5,6],[7,8,9]] и вопрос: какова сумма правого нижнего квадрата 2 × 2, то есть чисел 5, 6, 8, 9? Можно сложить их заново на каждый вопрос. Но можно один раз записать в каждой клетке сумму всего прямоугольника от левого верхнего угла сетки до этой клетки.

Тогда любой кусок собирается из четырёх таких сумм. Берёшь большую сумму до правого нижнего угла куска. Вычитаешь полосу над куском. Вычитаешь полосу слева от куска. Блок, который лежит выше и левее куска, попал в обе полосы, то есть вычтен дважды. Поэтому один раз прибавляешь его обратно. Четыре числа при любом размере куска.

Заранее посчитай для каждой ячейки одну накопленную сумму: сумму всего прямоугольника от левого верхнего угла сетки до этой ячейки. Храни эти суммы в таблице P. Добавь к ней сверху строку из нулей и слева столбец из нулей. Тогда формулы никогда не обратятся к индексу -1. В такой таблице P[i+1][j+1] хранит сумму от угла до ячейки (i,j).

Заполняют таблицу по включению-исключению. Блок, который заканчивается на (i,j), состоит из самой ячейки, блока прямо над ней и блока прямо слева от неё. Но эти два блока пересекаются в левом верхнем блоке, и он посчитан дважды. Поэтому его вычитают один раз:

P[i+1][j+1] = matrix[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]

Когда P построена, сумму прямоугольника считают той же идеей, только наоборот. Пусть левый верхний угол прямоугольника (r1,c1), правый нижний (r2,c2), оба включены. Возьми большой блок до правого нижнего угла. Вычти полосу над прямоугольником. Вычти полосу слева от него. Левый верхний блок ты только что вычел дважды, поэтому прибавь его обратно:

P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Проследим на сетке [[1,2,3],[4,5,6],[7,8,9]]. Запрос: правый нижний квадрат 2 × 2, (1,1)-(2,2). В нём ячейки 5, 6, 8, 9, сумма 28. По формуле:

• P[3][3] это вся сетка, 45.
• P[1][3] это верхняя строка, 1 + 2 + 3 = 6.
• P[3][1] это левый столбец, 1 + 4 + 7 = 12.
• P[1][1] это левая верхняя ячейка, 1.

45 - 6 - 12 + 1 = 28. Четыре чтения из таблицы, и неважно, четыре ячейки в прямоугольнике или четыре миллиона.

Построение P стоит O(rows × cols) и делается один раз. Потом каждый запрос стоит O(1): четыре чтения из таблицы и три сложения или вычитания. Для q запросов всего выходит O(rows × cols + q). Если на каждый запрос складывать ячейки заново, выйдет O(q × rows × cols). Память O(rows × cols) на таблицу. Обмен тот же, что в одномерных префиксных суммах, только в двух измерениях: один раз считаешь заранее, и потом каждый вопрос про диапазон решается сразу.

Интегральные изображения в компьютерном зрении: быстрое размытие, поиск признаков, поиск фрагмента по образцу. Суммы по областям в аналитических дашбордах и OLAP-кубах (многомерных таблицах для отчётов). Запросы о столкновениях и плотности на пространственной сетке. Любая сумма или среднее по прямоугольнику, который пользователь может выделить. К этому ведут все уроки про префиксные суммы. Когда один и тот же диапазон запрашивают много раз, заранее посчитанные накопленные суммы превращают каждый запрос из прохода по данным в простую арифметику. Включение-исключение переносит этот приём в два измерения и дальше.