🎓 Существует множество задач, где необходимо быстро вычислить некоторую сумму на заданном промежутке или отрезке. Есть даже соответствующая структура данных - Range Sum Query!
💡 И сегодня мы разберем одну из таких задач: быстрый подсчет суммы чисел в заданном промежутке в матрице.
#announcement #task_227 #решаем_задачки_дома
💡 И сегодня мы разберем одну из таких задач: быстрый подсчет суммы чисел в заданном промежутке в матрице.
#announcement #task_227 #решаем_задачки_дома
Telegraph
Анонс #227. Суммы в прямоугольнике
Задача: дана прямоугольная матрица размера NxM. Пусть (x1,y1) — координаты его левого верхнего угла, (x2,y2) — координаты его правого нижнего угла. Необходимо вычислять сумму всех чисел внутри такого прямоугольника. Входные данные: числовая матрица NxM, координаты…
Довольно часто необходимо оптимизировать подсчет каких то константных значений. В данной задаче мы рассматривали так называемые префиксные суммы в матрице. То есть для заданной матрицы мы подсчитываем префиксные суммы и уже их используем для быстрого (О(1) по времени) подсчета суммы произвольной подматрицы.
Полный разбор, как обычно, по ссылке ниже!
#task_227 #решаем_задачки_дома
Полный разбор, как обычно, по ссылке ниже!
#task_227 #решаем_задачки_дома
Medium
UniLecs #Task. Range Sum Query
Задача: дана прямоугольная матрица размера NxM. Пусть (x1,y1) — координаты его левого верхнего угла, (x2,y2) — координаты его правого…
Довольно интересная задача с техникой, которую стоит знать. Задача связана с предыдущей #task_227 с префиксными суммами!
#task_228 #решаем_задачки_дома
#task_228 #решаем_задачки_дома
Medium
UniLecs #Task. Sum X
Задача: дана квадратная матрица N*N. Найдите кол-во квадратных подматриц, сумма которых равна X.