На этой лекции мы разберем еще одну задачу на динамическое программирование. Она часто встречается как подзадача при реализации более сложных алгоритмов. Имеется поле размеры n на m, разбитые на единичные клетки. В клетках содержатся целые числа. Нам поступают запросы. Каждый запрос это прямоугольник со сторонами параллельными осям координат. Для каждого прямоугольника нужно вывести сумму чисел в нем. Пусть у нас строки нумеруются числами от 1 до n, а столбцы числами от 1 до m. Тогда каждый запрос - это четверка чисел и x1, x2 x y1, y2, - где x1, x2 от 1 до n. y1, y2 от 1 до m. x1, x2 - это номера строк, а y1, y2 - это номера столбцов, между которыми заключен наш прямоугольник. То есть прямоугольнику будут принадлежать все клетки с координатами x, y y которых x от x1 до x2, а y от y1 до y2, включительно. Для примера на рисунке, прямоугольник расположен в сроках с третьей по пятую и в столицах с третьего по шестой. Поэтому он будет задаваться четверкой чисел 3-5, 3-6. Подумаем, как решать эту задачу? Но здесь сразу приходит в голову наивное решение, для каждого запроса непосредственно двумя циклами перебирать те клетки, которые входят в этот прямоугольник и считать сумму чисел в них. Оценим время работы такого решения, в худшем случае у нас запрос будет совпадать с максимальным прямоугольником размеры n x m и поэтому оценка времени работы будет O большое от n, умножить на m умножить на количество запросов q. Это может быть достаточно много, поэтому давайте подумаем над более эффективным решением этой задачи. Сначала немного упростим задачу. Рассмотрим одномерный случай. Пусть у нас имеется полоса и нужно отвечать на запросы о суммах на под-отрезках. С первого взгляда непонятно, как это делать быстрее, чем за O от n. Но здесь можно ускорить ответы на запросы выполнив некоторые предпочет. Давайте посчитаем Si суммы на префиксах, на начальных отрезках длины i, то есть Si у нас будет сумма чисел полосы: а1+а2+ и так далее, +аi. Например, S1 будет просто равно а1, S2 будет а1+а2, S3 а1+а2+а3 и так далее. Мы можем пересчитывать значение этих частичных сумм при помощи динамического программирования, считать Si, как сумма предыдущая Si минус 1+ новое число аi, в качестве инициализации мы инициализируем значением ноль сумму S нулевое, потому что сумма нуля чисел у нас равна нулю. Дальше используя эти частичные суммы очень легко можно посчитать сумму на любом под-отрезке. Пусть у нас имеется отрезок от l до r, тогда сумма чисел на нем будет равна разности суммы чисел на отрезке от одного до r и суммы чисел на отрезке от одного до l минус одного. То есть ответ для такого запроса у нас будет разность S от r минус S от l минус один. Давайте рассмотрим код программы реализующую эту идею. Сначала происходит инициализация, мы значение S от нуля присваиваем нулю. Дальше мы в цикле считываем числа полосы Ai и сразу же вычисляем Si по формуле Si равно S i минус первому плюс Ai. Мы закончили предпочтет и начинаем ответы на запросы. Cначала мы читаем количество запросов q. Дальше мы в цикле читаем сами запросы l - это левая граница отрезка, а r правая граница и выводим ответ на запрос. S от r минус S от l минус одного. Давайте убедимся, что эта программа у нас будет корректно работать в крайних случаях, например, когда левая граница отрезка совпадает с левой границей полосы. Тогда l будет равно 1, а значит l минус 1 будет равно нулю, но S от нуля у нас подсчитано, это нулевая сумма, поэтому у нас выведится просто сумма S от r, которая равна сумме чисел на отрезке от единицы до r, собственно, что нам и нужно. Другой случай, когда у нас правая граница совпадает с правой границей полосы, тогда у нас S от l - это будет S от n, то есть тоже это значение у нас корректно подсчитано в данном случае. Мы получаем, что в крайних случаях все верно, выходов за границы нигде не происходит. Собственно, это все решение задач, только без чтения данных. Подведем итоги, нашей одномерной задачи. Сначала выполняется предпочтет за время у от n и после этого мы на каждый запрос можем отвечать за вывод единицы, потому что ответ на каждый запрос - это просто нахождение разности двух чисел. Замечу, что в наивном решение ответ на запрос происходил бы за время O от n. Это кстати распространенная идея в олимпиадных задачах. Если вам нужно отвечать на какие-то запросы, подумайте, может быть сначала стоит сделать предпочтет для того чтобы ускорить время ответа на каждый отдельный запрос. Вернемся теперь к двумерному случаю. Здесь напрашивается посчитать такие частичные суммы в прямоугольниках. Левый верхний угол, который совпадает с левым верхним углом поля, а правый нижний угол - это клетка с координатами i, j. То есть S от i, j у нас будет частичная сумма элементов в таком прямоугольнике. Используя эти частичные суммы, можно вычислять сумму чисел в любом под-прямоугольнике. Вот представим, что нам нужно вычислять сумму чисел в прямоугольнике, который на картинке обозначен буквой D. Тогда, мы вычисляют сумму во всем большом прямоугольнике А плюс В плюс С плюс D. Вычитаем из нее суммы в прямоугольниках А плюс В и А плюс С. После этого мы видим, что левый верхний прямоугольник, который обозначается А у нас вычелся два раза. Поэтому нужно его прибавить. В результате мы как раз в точности получаем сумму в прямоугольнике D. Здесь у нас используются только такие прямоугольники, у которых левый верхний угол совпадает с левом верхнем углу всего поля. В координатах эта формула будет иметь следующий вид, здесь S от x2, y2 это сумма в большом прямоугольнике. Из нее вычитаются суммы S от x1 минус 1 у2 и S от х2 у1 минус 1 и прибавляется сумма в маленьком прямоугольнике в левом верхнем углу, это S от x1 минус 1, y1 минус 1. Тогда у нас получится точно сумма в прямоугольнике, которой по вертикали ограничен координатами х1 и х2, а по горизонтали у1 и у2. Аналогичную идею можно использовать для предпочета самих частичных сумм S i, j. У нас S i, j будет получаться как сумма S минус первой j, плюс Si j минус первое. Дальше мы должны вычесть их общую часть Si минус первое, j минус первое и прибавить последний элемент в правом нижнем углу A ( i, j ). Эту формулу можно использовать для предпочета частичных сумм для всех клеток поля и дальше отвечать на запрос, как мы уже разобрали. Код программы по этой задаче вам предстоит реализовать самостоятельно.