UniLecs #Task. Range Sum Query
Задача: дана прямоугольная матрица размера NxM. Пусть (x1,y1) — координаты его левого верхнего угла, (x2,y2) — координаты его правого нижнего угла. Необходимо вычислять сумму всех чисел внутри такого прямоугольника.
Входные данные: числовая матрица NxM, координаты прямоугольника (x1,y1) — (x2,y2), где (1⩽x1⩽x2⩽N, 1⩽y1⩽y2⩽M); N*M⩽50000.
Вывод: сумму всех чисел в заданном прямоугольнике.
Пример:
- matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
Point1 = (1, 1), Point2 = (2, 3);
Output: Sum = 21 - matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
Point1 = (2, 2), Point2 = (3, 3);
Output: Sum = 28
Разбор
Для каждого элемента двумерного массива a[i][j] посчитаем сумму всех чисел, находящихся в прямоугольнике, правым нижним углом которого является a[i][j], а левым верхним углом которого является левый верхний угол таблицы. Обозначим такую сумму s[i][j]. Тогда ответом на запрос (x1, y1, x2, y2) будет значение:
S[x2][y2]−s[x1−1][y2]−s[x2][y1−1]+s[x1−1][y1−1]
Разберем на следующем примере. Пусть нужно узнать сумму чисел в красном прямоугольнике.
Тогда мы можем взять сумму чисел в оранжевом прямоугольнике (в формуле это S[x2][y2]), для которого уже посчитано значение и отнять у него сумму чисел в синем и зеленом прямоугольниках, для которых мы тоже знаем значения (в формуле это s[x1−1][y2] и s[x2][y1−1]).
Однако заметим, что у нас образовался квадрат, который мы вычли 2 раза, поэтому просто прибавим его (в формуле это s[x1−1][y1−1], на рисунке фиолетовый).
Реализация
https://gist.github.com/unilecs/57167bd094ebded10c68c85c0397c08d
