Линейные алгоритмы префиксные суммы (Фортунатов Василий) 20 ноября

Давайте начинать.

Сейчас, секунду, у меня проблемы со звуком.

Так, ну теперь, кажется, проблем быть не должно.

Скажите, меня слышно?

Все, хорошо.

Ну, сегодня у нас тема префиксной суммы.

Мы разберем обычные префиксные суммы и задачи, в которых их можно применять.

Посмотрим на многомерные префиксные суммы, разберем подробнее двумерные и посмотрим на разностный массив.

Потом вы порешаете контест из пяти задач формата муниципа,

на то, что мы сегодня пройдем.

Давайте так.

Кто из вас слышал, что такое префиксные суммы?

Ну, вижу, что часть слышала, но большинство нет.

Поэтому давайте определим массив префиксных сумм.

Ну вот, нам дан массив А, состоящий из целых чисел.

Он состоит из элементов А0, А1,

АН, длины N. Мы хотим посчитать массив PREF такой, что PREF IT это будет сумма первых И элементов.

То есть PREF 0 это 0, сумма нулевого количества элементов.

PREF 1 это А1, только один элемент суммируем.

PREF 2 А1 плюс А2.

И так далее.

Pref.i.

Да, давайте здесь будем в ноль индексации все делать, как это принято в языках программирования.

Ну и вот заметим, что для Pref.i мы суммируем по i-1 элемент включительно.

Ну и Pref.n это просто сумма всего массива.

Ну, посмотрим на свойства такого массива.

Во-первых, он состоит из n плюс 1 элемента, то есть имеет длину на 1 больше, чем массив a. А также pref it это сумма на полуинтервале 0 и в массиве a.

Что такое полуинтервал, я расскажу.

В общем, вот у нас есть отрезки, а b – это отрезок.

И вот в отрезке у нас принадлежат все иксы этому отрезку, включая обе границы.

А есть полуинтервал.

И иксы, которые равны правой границе, они не входят в этот полуинтервал.

Почему же мы храним именно так странно, почему не на отрезках, а на полуинтервалах, будет ясно чуть позже, когда мы будем рассматривать применение массива префиксных сумм.

Ну и вообще, обычно удобнее использовать полуинтервалы.

Мы посмотрим, почему.

Так вот, нетрудно заметить, что префытое – это будет сумма по всем i, которые лежат

от нуля до какого-то же.

Вот это будет превжи суммы по всем вот таким аитам.

Еще удобно думать про массив префиксных сумм, когда вот у нас есть наш массив,

Запишем его элементы в таких вот последовательных ячейках.

Мысленно представим.

Тогда массив префисных сумм можно записать в перегородках между этими ячейками.

То есть здесь будет P0, здесь P1, P2, P3, P4.

Так, давайте исправим на 0 индексацию.

P1 – это сумма всех ячеек, которые были до этого.

Да, вот здесь тоже должен быть нолик, потому что у нас ноль индексация.

P3 – это сумма всех ячеек, которые стоят до этой перегородки.

И это верно для всех вот этих перегородок.

Так полезно бывает представлять себе, когда вы решаете какие-то сложные задачи, где префиксные суммы – это лишь часть задачи, и вот чтобы в индексах не запутаться, удобно представлять вот так.

Хорошо.

Какие-то вопросы есть по тому, что такое массив префиксных сумм?

Если есть, можете задавать, я на них отвечу.

Хорошо.

И вообще, если будут вопросы возникать, вы можете в любой момент перебивать, задавать их, писать в чате, я буду отвечать.

Ну, собственно, давайте подумаем, как подсчитывать такой массив.

Сейчас я сотру что-нибудь.

Массив префиксных сумм – это массив сумм до какой-то аиты.

Массив префиксных сумм – это массив, где в ИТ-ячейке записана сумма элементов в А от нулевого до И-1 включительно.

Давайте я покажу на примере.

Пусть у нас был массив А – 1, 2, 4, 0, 3, 2.

И мы посчитаем массив префиксных сумм для него.

Первый элемент у нас всегда 0, это определение массива префиксных сумм.

Второй элемент это 1, потому что мы суммируем... Второй элемент это в 1 индексации, а в 0 индексации это первый элемент, это сумма одного первого элемента.

Второй элемент в 0 индексации будет 3, дальше 7, 7, 10 и 12.

Это будет массив префиксных сумм для массива А.

Почему называется префиксом?

Ну, потому что префикс – это сколько-то первых элементов нашего массива.

Там еще задали вопрос, что такое полуинтервал.

Полуинтервал – это как отрезок, только правая граница полуинтервала у нас не включена.

Чуть позже мы поймем, почему так удобно считать.

Давайте подумаем, как нам пересчитывать тогда преф и т. Как нам считать его?

Это не совсем как факториал, потому что факториал – это какая-то функция от числа.

А здесь мы считаем префиксные суммы для какого-то массива.

То есть для разных массивов будут разные массивы префиксных сумм.

Для массива А, который там равен 2, 1, 10, минус 2, массив префиксных сумм будет 0, 2,

3, 13, 11.

Так что, наверное, аналогия с факториалом здесь не совсем верна, потому что факториал все-таки зависит от одного числа, а здесь мы считаем целый массив для какого-то конкретного массива.

Для разных массивов a будут разные массивы префиксных сумм.

Понятно?

То есть it-ячейка в массиве pref – это сумма первых i элементов.

Вот.

Понятно, почему это не факториал?

Хорошо.

Когда я сотру примеры, и мы все же вернемся к подсчету массива pref.

Ну, можно было бы написать какой-то банальный алгоритм, где мы перебираем i от 0 до n. Я сейчас пишу псевдокод.

Это не код на каком-то там языке программирования типа C++ или Python.

Это просто, чтобы вы поняли суть.

Можно было бы написать какой-то такой код, но давайте заметим, что асимптотика его выполнения составит от n квадрат.

Потому что на первой итерации мы пройдемся по нуля элементам, на второй по одному, потом два и так далее до n. Алгоритм – это некоторая программа, которая принимает какие-то данные и должна что-то вывести.

Ну вот такая сумма, она будет примерно n квадрат.

Если у нас n будет порядка 10 в пятой, то, конечно, такой алгоритм будет работать очень долго, и в секунду такое точно не зайдет ни на C++, ни на Python.

Поэтому хотелось бы придумать что-то более умное.

Давайте подумаем, что.

Ну, заметим, что когда мы хотим посчитать префытое,

мы уже знаем pref и минус первое.

А что такое pref и минус первое?

Это сумма от нулевого до a и минус второго.

А сейчас мы хотим посчитать сумму от нулевого до i минус первого.

То есть такие две суммы отличаются всего лишь на одно слагаемое, вот это вот a и минус первое.

Поэтому можно сказать, что pref и t –

Это pref it-1 плюс a и минус первое.

И тогда, если мы проитерируемся по i от единицы до n, то получится вот так.

Сейчас я покажу код на C++, реализующий это, но суть вот такая.

То есть нам не обязательно каждый раз итерироваться по всем элементам массива, нам достаточно лишь посмотреть на то, что мы уже посчитали, и вот прибавить лишь один элемент.

Ну и да, перед этим всем нам нужно вот здесь написать, что pref 0 равно 0.

Для нулевого элемента, который всегда равен 0, мы как бы явно скажем это.

Собственно, вот реализация на языке C++.

Это то же самое, что мы написали.

Только, ну да, то же самое.

Есть какие-то вопросы по тому, как писать?

Ну да, люди должны так оптимизировать, но все же уровень разный, хотелось бы, чтобы все это осознали.

Ну, хорошо, что всем понятно.

Давайте теперь перейдем к применению массива префисных сумм.

Вообще, зачем мы это считаем?

Для чего это нужно?

Вот это очень хороший вопрос, давайте это поймем.

Вот пусть нам дан массив a, dn, также состоящий из элементов от a0 до an-1.

И нам приходит ку запросов.

Каждый запрос – это посчитать сумму на полуинтервале от l до r. Что такое сумма на полуинтервале от l до r?

Это al плюс al плюс 1, плюс и так далее, плюс ar-1.

Это полуинтервал, поэтому r границы у нас не включается.

Так, это q у меня написано.

Вот.

Ограничения таковы, что n и q до 10 в пятой.

Ну, какое мы могли написать бы наивное решение?

Для каждого запроса просто сделать там for i от l до r минус 1 и там к сумме

прибавить a и t. Но асимптотика такого алгоритма будет o от n на q. И при n и q порядка 10 в пятой, это будет 10 в десятой, что опять же очень долго.

Если у нас все запросы будут просто l равно 0, r равно n, то наша программа будет работать очень долго, дольше, чем 1 секунду уж точно.

Поэтому так мы написать не можем.

Давайте подумаем, как это написать, как такую задачу решать быстро с помощью массива префиксных сумм.

Вот да, там уже в чате пишут правильный ответ.

Давайте поймем, почему это действительно так.

Давайте посмотрим, что было бы, если бы во всех запросах l было равно 0.

Тогда нас бы интересовало, что a0 плюс a1 плюс ar минус 1.

А это буквально по определению pref r.

То есть если бы во всех запросах l было равно 0, мы могли бы просто выводить pref r. А вот если l не равно 0, то не совсем понятно, что делать.

Ну давайте тогда посмотрим, чему равно pref l. И чему равно pref r снова.

Давайте посмотрим.

Вот эта вот часть prefr, вот эти вот слагаемые, это в точности наш ответ.

Скажем, что это равно s. А вот это вот, ну это в точности совпадает с prefl, которое написано выше.

Ну, несложно заметить, что тогда prefr равно prefl плюс s, и тогда s наш ответ равен.

просто равен pref l минус pref l. Давайте посмотрим.

Это как раз пример, демонстрирующий, почему нам удобны полуинтервалы.

Если бы мы хранили наш массив pref без нуля в начале, то есть было бы pref 0 равно a0, pref 1 равно a0 плюс a1 и так далее, тогда не совсем понятно было бы, как отвечать на запросы, когда l равно нулю.

Нам бы пришлось отдельно ифать случай, что не нужно вычитать минус первый элемент и так далее.

Все это так сложно.

А вот в данном случае у нас очень красивая формула.

У нас нет никаких плюс-минус единичек.

То есть не надо здесь делать минус один или плюс один.

У нас просто красивая простая формула.

И когда вы будете писать сложные задачи, где префиксные суммы являются лишь частью большой задачи, это будет меньше вас запутывать и будет проще допустить какую-то ошибку.

Я видел, там кто-то поднимал руку.

Если у вас есть вопрос, можете просто написать или задать голосом, не поднимая руки.

Какие-то вопросы есть, как решать такую задачу?

Всем понятно?

Ну, хорошо.

Давайте пойдем дальше и подумаем,

Ну, вот сумма – это слишком скучно.

У нас могут быть какие-то другие запросы.

Например, считать минимум на отрезке или максимум, или наибольший общий делитель ГЦД, или не меньше общекратное LCM, или там побитого И, что-то вот такое интересное произведение, может быть.

Давайте поймем, что мы умеем считать.

Ну, XOR я сейчас объясню, да.

Какие функции мы можем считать?

На самом деле, главное условие – это…

чтобы функция могла быть выражена как разность или какая-то функция от двух префиксов.

Так, 40 исключающий или, я сейчас подробнее расскажу об этом.

Давайте вот посмотрим на примере минимума.

Можно ли считать минимум?

Пусть есть массив a0, a1, a-1.

И у нас та же самая сдача, только на отрезке мы хотим считать не сумму, а минимум.

Ну, если бы мы построили массив PREV, где PREV и T хранит минимум среди первых и элементов,

то тогда, ну вот давайте посмотрим на каком-нибудь примере.

Пусть был массив 1, 0, 2, 4, 3.

Тогда массив prep был бы, ну, первый элемент, допустим, какой-то плюс бесконечность, просто чтобы удобно было считать.

Второй элемент 1, потом 0, 0, 0, 0, 0.

Так, сейчас я не ошибся в количестве нулей.

Сейчас, секунду.

Да, все верно.

То есть у нас как только нолик встретился в массиве, так вот до конца он и будет.

И пусть мы хотим узнать минимум на вот таком отрезке 4,3.

Ну тогда мы бы хотели в массиве префиксных сумм посмотреть на вот какой-то такой отрезок.

Тогда казалось бы, что у нас будет ноль.

Очень странно, короче.

Почему же так?

Ну потому что у нас для минимума нет...

Обратимые операции.

То есть мы не можем по двум значениям… Вот, допустим, мы знали, что минимум x и y равно z. Если мы знаем x и y, можем узнать z. Если мы знаем x и z, можем ли мы узнать y?

Ну, нет.

Нет.

Потому что если у нас было известно, что минимум x и 0 равен 0, то чему могло бы быть равно x?

Ну, оно могло быть равно 0, или 1, или 100, или 10 в 9, и вообще любому числу, которое не меньше 0.

Собственно, на примере, который я вам продемонстрировал, вот это и вид.

Мы не можем по результату функции и одному ее аргументу понять второй аргумент.

Так, понятно, почему мы не можем считать минимум на префиксе?

Не особо.

Ну, хорошо.

Давайте попробую еще раз объяснить.

Значит, что нам было важно, когда мы считали сумму?

Какое вообще свойство там использовалось?

Что мы можем ответ на отрезке или полуинтервале, ну, не важно, напишем полуинтерваль.

Ответ на полуинтервале получали как...

какую-то вот функцию от значений на двух префиксах.

Вот.

Почему мы могли там так делать?

Ну, потому что мы знали, что для сложения есть обратная операция.

Это вычитание.

Для минимума такой операции не существует.

Вот здесь я продемонстрировал.

Если мы знаем, что у нас на вот таком префиксе минимум равен 0, потому что вот здесь у нас лежит… Сейчас, секунду.

Заданную нарисую.

Вот на таком префиксе минимум равен 0.

Аналогично той задаче мы бы хотели посмотреть на значение pref l. Вот оно.

Здесь минимум тоже равен 0.

И как нам вообще тогда вычислить минимум на отрезке?

Ну, вообще непонятно.

Потому что как у нас вычисляли следующее значение?

Вот мы знали, что pref l равен 0.

Затем мы считали pref l плюс 1, который равен минимум из 0 элемента a, l, t.

И считали, и так далее.

Но как бы так у нас все числа были не меньше нуля, то все вот эти pref l плюс 1, pref l плюс 2 и так далее были тоже ноликами.

И pref r в том числе.

И в таком случае не совсем понятно, как узнать какую-то информацию об элементах на отрезке lr.

У нас нолик меньше всех элементов на этом отрезке.

Он уже как бы перекрыл их всех.

Мы не можем понять, какие значения здесь были.

Единственное, что мы можем сказать, ну, все значения, они были не меньше нуля.

Если бы они были меньше нуля, тогда у нас префер было бы равно какому-то числу меньше нуля.

А так мы ничего про них не можем сказать.

И таким образом мы никак по значениям на префиксах не можем восстановить значения на отрезках.

Так стало понятнее?

Если нет, сейчас мы разберем...

другую функцию.

Смотрите, давайте сейчас тогда разберем умножение на отрезки, произведение чисел на отрезки.

И тогда, может быть, станет чуть понятнее.

Секунду.

Давайте считать, пусть у нас есть такая же задача, только нужно искать не минимум на отрезке, а произведение элементов.

И, допустим, все элементы у нас

больше нуля, тогда как бы мы могли решать эту задачу?

Сказать, что префыта – это не сумма, а произведение элементов на префиксе.

Тогда как бы мы хотели узнать функцию произведения на полуинтервале?

Давайте скажите мне по аналогии с префиксными суммами.

Да, действительно поделить.

Потому что, ну, как мы обратную операцию к плюсу можем взять в минус, а здесь можем взять деление.

Вот.

Тогда произведение на полуинтервале, прошу прощения, lr, будет равно вот такому числу.

Важно заметить, что у нас тут все числа больше нуля, потому что если бы было число равное нулю, то у нас...

могло бы возникнуть деление на 0, и такое мы считать, ну, мы не можем делить на 0.

А также важно отметить, что, ну, если мы пишем на языке C++, например, у нас тип данных long-long, ну, числа больше, чем 2 в 64, ну, а это примерно 10 в 19.

Такие числа long-long у нас замечать не может.

Но если мы возьмем массив А, состоящий из кучи двоек, допустим, из 100 двоек, то тогда у нас pref n уже будет равно 2 в сотой.

Мы просто перемножим все эти двойки.

И такое число мы просто не сможем хранить в стандартном типе данных.

Поэтому зачастую в задачах вас будут спрашивать ответ по модулю, какому-то простому модулю, и тогда вам нужно делить и умножать по модулю.

Это чуть более сложная тема, о ней вы узнаете, я думаю, чуть позже, на теории чисел какой-нибудь.

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

Ну, например, C++.

Да, тут есть еще одно небольшое отличие, когда мы считаем произведение на префиксах,

Скажите, чему должно быть равно прев 0 в данном случае, когда мы считаем произведение?

1.

Это правда?

Ну, логично.

Почему?

Единица – это такой нейтральный элемент.

То есть, когда мы считали сумму, у нас нейтральный элемент был 0.

Что такое нейтральный элемент?

Давайте запишу.

Если функция от х и у равна у для любого у.

Ну, написано очень формально, но глобально, я думаю, вы понимаете, что такое нейтральный элемент.

Так, можете, пожалуйста, повторить про остаток отделения при умножении?

Ну, еще раз.

Если у нас дан массив А, например, длины 100, и он состоит из всех двоек,

то тогда у нас последняя префиксная сумма, ну на самом деле уже не сумма, а произведение, последний элемент в этом префиксном массиве, он будет равен 2 в сотой.

2 в сотой – это очень большое число, которое точно больше, чем 10 в 19.

А это значит, что это число мы не сможем уместить в стандартных типах данных в языках программирования.

Это значит, что мы такое посчитать не сможем.

Поэтому обычно в задачах,

Вас требует вывести ответ по какому-то простому модулю.

То есть, ну что такое модуль?

Когда вам нужно вывести a0 на a1 на a и t, процент mod.

Процент – это остаток отделения, где mod – это фиксированное число, данное там в условии.

Вот.

То есть вам тогда и делить тоже надо так.

В одной из задач нельзя комбинировать языки программирования.

Вы отсылаете код под одним компилятором.

Хорошо, вот понятно про произведение.

Да, можно брать модуль, когда перемножаешь.

Давайте я продемонстрирую.

Если мы хотим перемножить числа x и y, то можно сделать вот так.

сайт-табличкой, сейчас мы его еще обсудим, да.

Ну, если вы пишете там на C++, то, конечно, вам нужно еще там к long-long это сконвертировать, если вы перемножаете int.

Но это уже особенности языка, я думаю, вам их объяснили на лекции позавчера.

Вот, мы так вот перемножаем числа.

Ну, вообще, как бы, если ты их перемножишь и возьмешь остаток, это будет то же самое, если ты

Возьмешь остаток, а потом перемножишь.

Это эквивалентные записи.

Но в чем может быть проблема?

В том, что x и y могут быть, например, 10 в 18.

Тогда x на y – это 10 в 36, что, очевидно, превышает long-long.

Мод – это константа, которая дана в условии.

Это просто какое-то число.

Зачастую вы можете увидеть 10 девятый плюс 7, или 10 девятый плюс 11.

Плюс 9, да, плюс 11 не дают.

Мод – это просто фиксированное число.

Нас так просят делать, чтобы числа умещались в стандартные типы данных.

Да, это очень справедливое замечание, но обратный элемент по модулю, я думаю, здесь не все знают.

Я просто сказал это на будущее вам.

Каждый раз можно делать x равно y на мод.

Это уже детали реализации.

Давайте перейдем дальше.

Что мы еще можем считать?

Есть исключающее или.

Что такое исключающее или?

Зачем к мод число прибавляется?

Там к mod не прибавляли число.

Зачем к mod число прибавлять, я понял.

Если вопрос про это.

Обычно число mod делают простым.

Это нужно, чтобы выполнялись некоторые математические требования.

Но вы это узнаете потом на лекции по теории чисел.

Сейчас мы не будем в это углубляться, это не совсем касается префиксов.

Ведем операцию побитого исключающего или, то есть ксор.

Чаще всего задача называется именно так.

Ну, значит, да, вот тут уже написали, он обозначается вот так в записях и вот такой вот крышечкой в языках программирования Python и C++.

Ну, значит, XOR для битов, то есть нулей и единичек, определяется вот так.

Вы можете смотреть на это как на неравно.

То есть ноль не равен нулю – это неправда, поэтому ноль.

Ноль не равен единице – это правда, оно равно единице.

Один не равен нулю – да, это правда, поэтому значение равно единице.

Один не равно единице – это неверно.

Ну да, или можно так исключающе, или оно равно единице, только когда один бит равен единице.

Да-да-да, вот в чате все правильно пишут.

Ну как же определить ксор для чисел не 0,1?

Ну, надо записать их двоичную запись и просто для каждого бита применить операцию XOR.

Ну, вот для таких вот двух чисел XOR будет вот такой.

Ну, и затем конвертировать это в десятичную запись.

Можете XOR повторить, да.

XOR, вот, он обозначается вот таким плюсиком в кружочке в записях и крышечкой в языках программирования.

Вот таблица истинности для XOR.

Да, вот мы как бы сначала его определяем для битов, то есть для нулей и единичек.

И тогда он будет равен единице и только в том случае, когда ровно один из аргументов равен единице.

Либо же можно смотреть на это как на операцию неравно.

Для битов это будет то же самое.

А затем мы определяем побитовое исключающее или, когда мы для каждого бита из двух чисел определяем функцию XOR.

Вот.

Ну, здесь я вот показал вам пример.

Давайте скажите мне, какая будет обратная операция к XOR.

То есть для плюс это было минус вычитание, для умножения это было деление, а для XOR пишут что равно.

Ну, давайте попробуем проверить, правда ли, что это равно.

Ну вот, посмотрим на первый.

Мы знаем, что у нас x сор 0 равно 0.

Вы говорите, что равно.

0 равно 1, из этого следует 0 равно 0, значит, x равно 1.

Но это неправда, у нас x должно было быть равно 0 здесь.

Да, вот как правильно пишут в чате, это не равно.

а не равно – это как раз-таки XOR.

Обратная операция к XOR – это сам XOR.

Но в этом нетрудно убедиться, просто подставив таблицу истинности еще раз в чиселке.

Скажите, чему будет равен нейтральный элемент для XOR, когда мы считаем при F0?

Для нейтрального элемента должно выполняться, что XXOR0 равно X.

Да, действительно, нейтральный элемент для XOR – это 0.

Все, мы знаем все, чтобы написать префиксные XOR.

Какие-то есть вопросы?

Ну, хорошо, здесь вопросов нет, если что, задавайте.

Значит, вам будет выслана презентация, поэтому еще потом посмотрите на этот слайд.

Ну вот, для суммы произведения XOR мы разобрались.

Теперь, может быть, стало немного понятнее, почему мы не можем минимум считать на отрезке.

Кому там было непонятно, напишите.

Если кому-то непонятно, скажите.

Вот сейчас мы еще раз рассмотрим пример, который объясняет, почему нельзя.

Что такое GCD?

GCD – это нод.

Наибольший общий делитель двух чисел.

GCD – это его английское название.

Кажется, greatest common divider.

В языках программирования у вас обычно GCD как раз называется.

Ну да, GCD есть и плюс-плюс, но при этом GCD на отрезке вы читать не можете.

Как им пользоваться?

Ну, вы можете почитать это в документации, но просто вот так пользоваться.

GCDXY.

Еще раз про минимумы, максимумы.

Всем понятно, почему мы считать не можем?

На матрицах, как это мы обсудим чуть позже.

Ну все, значит, переходим дальше.

Но перед этим давайте вот пришлем какие-нибудь задачки.

Дан массив А, элементы которого могут быть отрицательными.

Нам необходимо в нем найти отрезок с максимальной суммой.

Давайте сначала решим более простую версию задачи.

Как решать задачу, если все элементы не отрицательные, то есть положительные или ноль?

Тогда как нам найти ответ?

Напишите кто-нибудь.

Да, это правда.

Это просто сумма всего массива.

Ну, думаю, понятно почему.

Если мы не взяли какие-то элементы, можем их взять, тогда ответ точно не уменьшится, и мы ответ не сделаем хуже.

Теперь поймем, как решать задачу здесь.

Ну, давайте заметим, что такое отрезок.

Вот мы хотим рассмотреть сумму на отрезке LR.

Во-первых, можно перейти от отрезка к полуинтервалам, как мы это сегодня часто будем делать.

И вот сумма на полуинтервале LR, это, как мы выяснили,

Pref R минус Pref L. Я буду писать P, сокращать дальше.

Вот.

То есть, на самом деле, к чему свела задача?

Нам нужно на массиве префиксных сумм найти разницу, найти каких-то два элемента, что вот их разница вот такая вот максимальная.

Можно делать два указателя.

Ну, мы сделаем чуть по-другому.

Но два указателя тоже, наверное, можно написать.

Давайте пусть мы знаем PR.

Вот пусть мы будем итерироваться по R от единицы до N. Включительно.

Почему от единицы до N?

Вот, да, здесь почти правильно написали.

Выбираем самый большой PR и находим самый маленький PL.

Ну, а вдруг будет такая ситуация, что вот у нас есть массив P. Здесь...

находится максимум, а здесь находится минимум.

Тогда, очевидно, мы не можем взять... Да, вот здесь правильно написали.

Очевидно, мы не можем взять l больше, чем r. Такого полуинтервала попросту не существует.

У нас l должно быть меньше и равно, чем r. То есть, когда мы идем по r от единицы до n... Сейчас, секунду.

Нам нужно обновить ответ...

как максимум из уже текущего и PR минус минимальное PL.

То есть нам нужно идти и поддерживать минимальное PL среди всех, которые мы уже рассмотрели.

Для этого можно завести какую-то переменную кур, которая изначально равна 0, а затем просто обновлять кур равен минимум.

Из cur и pl.

Почему cur мы изначально инициализируем нулем?

Ну, потому что мы всегда можем взять l, равное 0, то есть нулевой элемент префиксной суммы.

Какие-то вопросы есть по этой задаче?

Да, какие вопросы?

Непонятное решение, еще раз объясните.

Хорошо.

Еще раз.

Мы хотим найти отрезок с максимальной суммой.

Отрезок – это полуинтервал, то есть LR.

Как мы уже знаем, что сумма на таком отрезке – это PR минус PL.

То есть мы хотим максимизировать вот такое значение.

Но давайте будем перебирать правую границу.

Будем перебирать от 1 до N. Скажу, почему.

Вот мы зафиксировали PR.

То есть вот это вот какое-то константное число.

Мы его не можем сейчас изменить, когда зафиксировали R. Тогда что нам нужно сделать, чтобы PR минус PL было максимальным?

Мы хотим минимизировать PL, чтобы отнять от PR как можно меньшее число.

Нам выгодно так делать.

Получается в коде, когда она считается вместо… Да, это правда.

Здесь мы напишем кур.

Сейчас PR минус кур, да.

Мы зафиксировали PR и хотим выбрать минимальное PL.

PL среди всех L, которые меньше, чем R. Расскажу, почему строго меньше.

Потому что вот такой полуинтервал – это пустой полуинтервал.

Он нас не очень интересует.

Мы не хотим рассматривать пустой отрезок.

Именно поэтому мы хотим идти и поддерживать минимальную PL.

Если все отрицательные.

Ну, смотрите, тут в зависимости от задачи может быть.

Ну, может быть такая задача, что отрезок должен быть не пустой.

Вот это такая задача.

То есть если массив минус 1, минус 3, минус 10, нам все еще нужно вывести минус 1 в данном случае.

Ну, могут быть разные задачи.

В конце вы всегда можете сказать, что ответ – это максимум из посчитанного ответа и нуля, если от вас требуется иное.

Теперь стало понятнее, почему это решает задачу.

Если отрезка должна быть определенной длины, то как?

Answer равно max элемент.

Ну, это в случае с этим, да.

То есть мы перебираем правые элементы, ищем максимальный, потом ищем минимальный левый и берем их разность.

Не совсем.

Мы не ищем максимальный PR.

Мы перебираем все правые границы.

Мы не знаем, какая граница правая оптимальна.

Мы перебираем их все.

И среди всех таких, вот мы для каждой границы R смотрим минимальное PL, которые у нас были до этого на префиксе.

То есть вот у нас есть цикл.

Время работы данного алгоритма от N. Как кур считается?

Кур – это переменная, которую мы подсчитываем, идя слева направо, перебирая R. И мы хотим, чтобы…

Кур – это минимум префиксных сумм на префиксе, который мы уже рассмотрели.

То есть изначально кур равен 0, а затем мы в циклике пересчитываем кур.

А здесь, еще раз напишу, мы пересчитываем ответ.

Там, где считается кур, считается PL.

Это PL минус 1.

Да, вот, спасибо.

Это очень хорошее замечание.

Только не PR-1, а просто PR, да.

Потому что мы вот считаем на префикс.

Остались вопросы какие-то?

Почему время n, долго n?

Время от n. У нас нет никаких сортировок, бинпоисков.

Мы просто за линию идем, подсчитываем...

Элемент минимальный на префиксе.

Откуда должен взяться лог?

Мы сначала за линию считаем, если L больше R, видимо.

L не может быть больше R. Именно поэтому мы считаем значение кур именно на префиксе, то есть до R элемента.

То есть вот у нас есть массив P, мы сейчас зафиксировали массив R. И вот на префиксе до него мы считаем,

Минимум по всем PL таким, что L меньше, чем R. Мы считаем минимум PL.

L не может быть больше, чем R по условию.

Это не совсем понятно, что это за отрезок.

Еще вопросы.

Это довольно классическая задача, довольно полезное применение массива префиксов в случае.

Всем все понятно, да?

Ну, давайте переходить дальше.

Решим следующую задачу.

Нам дан массив А и какое-то число х. Х – это зафиксированное число в условии.

Нам нужно найти такой отрезок, что сумма на нем равна х. Либо сказать, что такого отрезка не существует, либо вывести любой такой отрезок.

Ну, давайте еще расскажем, что любой отрезок, то есть сумма на любом отрезке, можно представить как сумма на полуинтервале PR минус PL.

Нам нужно, чтобы PR минус PL было равно х. Давайте опять зафиксируем PR.

Тогда выразим PL как PR минус х. То есть для фиксированного

R нужно проверить, существует ли такая граница L меньше, чем R, что PL равно PR минус X. PR минус X – это как бы константом.

Это число, которое мы точно можем посчитать для R. Да, действительно.

Давайте, вот тут написали ProSet, давайте поймем, как это писать.

Ну, переберем правую границу от единицы до n. И будем поддерживать какой-то set.

Назовем его опять кур от слова current, текущий.

И нам нужно проверить, правда ли, что в сети лежит число pr-x.

Если да, то ответ «да».

И можно, в принципе, заканчивать выполнение программы.

Иначе нам нужно добавить «pr», так как мы опять же на префиксе подсчитываем этот сет.

И, может быть, мы найдем ответ дальше.

Два указателя можно сделать.

Как ты хочешь сделать два указателя?

Если ты хочешь решить вот таким образом…

Если ты хочешь решить вот таким образом, то время выполнения будет от n квадрат.

Это очень долго.

Можете на коде показать?

Давайте я сейчас подемонстрирую код.

Секунду.

Так, скажите, вам видно?

Должно быть да.

Хорошо.

Давайте напишем это.

Я буду писать на языке C++.

Если будут какие-то вопросы по реализации, то задавайте.

Ну вот, мы считываем наш массив и число x. Считаем его префиксную сумму.

LL – это long-long сокращение, если что.

Почитали его префиксные суммы.

Теперь мы хотим хранить какой-то set, стоящий из LL.

Это кур.

Это префиксные суммы, которые нам уже встретились на префиксе.

То есть кур – это сет, который мы будем пересчитывать в процессе выполнения программы.

Это не что-то зафиксированное до момента начала цикла.

Нам нужно проверить, правда ли, что в кур существует элемент pref r минус x.

Вот это эквивалентно тому, что элемент существует в курсе.

Тогда ответ yes.

Ну и в конце нам нужно прибавить нашу текущую префиксную сумму, потому что мы хотим на префиксе подсчитывать.

Но если мы за все время цикла не смогли найти такого, то это значит, что такой префиксной суммы у нас не существует.

Такого отрезка не существует.

Если нет отрицательных чисел, то можно сделать два указателя.

Да, это правда, но проблема как раз в том, что могут существовать отрицательные числа.

Тогда инвариант, который должен выполняться для двух указателей, уже не выполняется, и поэтому два указателя в данной ситуации использовать нельзя.

Ровно так же, как нельзя использовать, например, bin поиск, потому что функция будет не монотонна.

Точка count тоже можно использовать, да, это под капотом,

То есть в реализации C++ каунт работает точно так же, как вот мной здесь написано.

Почему кур именно set?

Мы хотим как-то быстро узнавать, была ли у нас на префиксе необходимая префиксная сумма.

Как мы это можем делать?

Ну, мы можем, конечно, пройтись циклом и проверить, но это будет слишком долго.

Это будет эквивалентно тому алгоритму, который рассказывал я вот ранее и объяснял, почему он работает за от n квадрат.

Мы хотим узнавать как-то быстрее.

Ну, какая структура данных позволяет нам за от log n или за от единиц, ну, как-то быстрее, чем за линию, узнавать, существует ли какой-то элемент.

Ну, это std set в heap++ и set в p2.

Anordered set можно, да.

Вот время работы такого алгоритма равно от n log n. Если мы здесь напишем anordered set,

Тогда у нас set будет работать за константу, и общее время выполнения программы будет от n. Это будет быстрее, да.

Какие-то вопросы есть?

Вот, мы получили, что наша программа работает даже быстрее, чем если мы использовали там bin поиск для при положительных числах.

Так, ну если всем понятно, можем переходить дальше.

Следующая задача.

Уже не задача, а более общая идея.

Вот там спрашивали, как считать такое на матрице.

Ну вот, двумерный случай префиксов SUB.

Мы научились считать префиксные суммы на одномерном массиве, но что, если мы хотим считать в каком-то n-мерном пространстве?

Что, если у нас массив состоит двумерный или трехмерный или четырехмерный?

Давайте рассмотрим, как это делать на массиве двумерном.

Значит, двумерный массив префиксных сумм b мы определим следующим образом.

Матрица, ну, матрица, это можем воспринимать как...

Вектор векторов в C++ или массив массивов листов в Python.

Здесь написана сложная формула, но на самом деле она намного проще понимается.

Вот эта вот i плюс первая, g плюс первая ячейка массива b, она равна сумме всех элементов,

которые стоят в нашей табличке выше и левее текущего элемента.

В принципе, по аналогии с префиксными суммами на одномерном массиве мы считаем плюс-минус так же.

Понятно, что такое массив префиксных сумм в двумерном случае.

Плюс-минус.

Еще раз.

Давайте рассмотрим на каком-нибудь примере.

Пусть была такая табличка.

Мы также, как и в случае с одномерными префиксными суммами, добавим нули в начале.

Зачем это нужно?

Ну, опять же, для удобства формул.

Чуть позже мы убедимся, почему это удобно.

Тогда у нас здесь был размер 2х3, а станет 3х4.

Но вот здесь в этой ячейке 1, потому что мы просто суммируем вот этот элемент.

Здесь мы хотим просуммировать 1 и 2.

1 плюс 2 – это 3.

В этой ячейке мы хотим просуммировать всю первую строку.

Сумма равна 6.

Здесь мы хотим просуммировать только лишь первый столбец.

Сумма равна 5.

Здесь, ну вот читаем вот в этой табличке 2 на 2, 1 плюс 2 плюс 4 плюс 0 – это равно 7.

И в этом элементе у нас здесь сумма…

чисел всей таблицы, она равна 1 плюс 2 плюс 3 плюс 4 плюс 0 плюс минус 1.

Это, кажется, 9.

Вопросы?

Теперь стало понятнее, как мы определяем массив префиксных сумм?

Да, хорошо.

Вижу, кому было непонятно, стало понятно.

Зачем же он нужен?

Ну, собственно, для того же,

Секунду.

Для того же, для чего я нужен был обычный массив префиксных сумм, считать сумму на отрезке.

В данном случае на подтабличке, под матрице, под прямоугольнике.

Встречаются разные наименования.

Но для начала давайте поймем, как считать такой массив.

Конечно, мы могли бы считать его, что называется, в лоб, то есть просто для конкретной дичейки ижи пересчитывать...

за от n квадрат полностью все элементы, которые стоят в нужном углу.

Но это будет работать очень долго.

Хотелось бы что-то побыстрее.

Давайте поймем, как.

Вот это вот наш массив префиксных сумм.

Допустим, мы хотим посчитать сумму вот в этой ячейке, которая находится в строке i и в столбце в j. А через dp с рекурсией, ну, на самом деле, то, что мы сейчас напишем, действительно будет

своего рода динамическим программированием, но рекурсию, мне кажется, здесь не очень удобно использовать, просто потому что, во-первых, рекурсия работает дольше, во-вторых, если ты напишешь самую глупую рекурсию без мемоизации, то есть запоминания предыдущих ответов, то у тебя будет вообще очень-очень долго работать.

Это будет сложно, поэтому здесь есть намного более простой подход, но это действительно ДП.

Но мы будем использовать не рекурсию, а обычный подсчет динамики назад.

Так, мы хотим посчитать и ту же ту ячейку массива префиксных сумм.

Но давайте заметим, что если мы посчитали сумму вот здесь, это что за элемент?

Это элемент pref и g-1.

И посчитали сумму, допустим, вот здесь.

Ой, сейчас что-то появилось.

Секунду, я уберу это.

и, допустим, мы знаем вот это вот.

Это прев и минус 1g.

Тогда заметим, что сумма вот таких штучек, это мы посчитаем вот это вот, посчитаем вот это, но вот этот вот прямоугольничек у нас посчитается два раза.

Знаем ли мы сумму в этом прямоугольнике?

Ну да, знаем.

Это прев и минус 1, g минус 1.

Тогда для того, чтобы вычислить прев и g, давайте просуммируем прев и g минус 1.

Прев и минус 1 g. Вычтем их пересечение, вот этот прямоугольничек, потому что он подсчитан дважды.

И заметим, что мы совсем забыли про этот одиночный элементик, стоящий в углу.

Мы просто можем прибавить a и t житы.

И j – это и t житый элемент в исходной матрице a, для которой мы считаем префиксный сумм.

Понятно, почему это верно.

Кстати, я еще раз чуть подробнее объясню, почему.

Но я вижу, что непонятно кому-то.

Смотрите.

Значит, еще раз.

Что мы хотим посчитать?

Мы хотим посчитать сумму вот на таком прямоугольнике.

Это то, как мы определили префиксные суммы.

Но что я говорю?

Давайте посчитаем сумму вот на таком прямоугольнике.

Допустим, мы ее уже знаем.

Что это за сумма?

Ну, это сумма pref и g-1.

То есть

Видите, мы как бы на время забыли про житый столбец, и вот посмотрели, до G-1 включить.

Такую сумму мы уже знаем.

Хорошо, давайте посмотрим.

Секунду.

Да, что-то там стукнулось.

Нет, что-то знакомо.

Все, спасибо.

Что такое динамическое программирование, вы это узнаете на лекции потом.

Здесь думайте про это не как про динамическое программирование.

Мы просто подсчитываем суммы.

Можно же посчитать суммы каждой строки и сложить их затем.

Григорьев Александр, ты предлагаешь сначала посчитать префиксные суммы для каждой строки, а затем их сложить также при помощи префиксных сумм?

Да, такое решение тоже есть.

Это второй способ.

Вот такой способ, как я рассказываю сейчас, он более классический, и когда вы будете его писать, ну, вы будете писать его более быстрее, потому что вам нужно будет написать всего лишь два цикла и одну формулку подсчета, нежели чем создавать двумерный массив, еще один, там какие-то префиксные суммы подсчитывать.

Вы, наверное, потратите от n квадрат дополнительной памяти, что может быть критическим в задачах с большими ограничениями.

Почему нельзя просто взять pref и t жито?

Смотрите.

Мы сейчас подсчитываем как раз-таки pref и t жито.

Мы не можем ее взять, потому что мы считаем ее.

Я объясняю, как посчитать pref и t жито.

Но не в лоб, просто пересчитав все элементы, которые находятся под прямоугольники, а вот через какие-то другие значения pref сум.

Ровно так же, как мы в одномерном случае считали pref и t через pref и минус первое.

Нам же не нужно было весь префик заново пересчитывать.

а именно в моменте составления матриц.

Что в моменте составления матриц?

Не совсем понял твой вопрос.

Я сейчас рассказываю, как посчитать pref и t житое через уже посчитанные значения.

Это понятно?

Пока мы не знаем pref и t житое.

Сейчас мы не знаем прев в t житое, но мы знаем прев и t жи минус первое, и знаем прев и минус первое житое, и знаем прев и минус первое жи минус первым.

И я рассказываю, как вот через эти три величины вычислить прев и t житое.

Понятно, что мы хотим посчитать?

Все окей.

Значит, как мы это будем считать?

Посмотрим на сумму здесь.

Это pref и g-1, то есть вот это вот.

Посмотрим на сумму в другом прямоугольничке, вот здесь.

Это pref и g-1.

А, ты заголовок не пришел?

Ну хорошо, да, бывает.

Сейчас мы, еще раз напомню всем, кто, может, потерялся, мы учимся считать массив префиксных сумм двумерный для двумерных массивов.

Вот.

Мы знаем pref и g-1.

Это...

Сумма вот на таком прямоугольничке.

Но если мы просуммируем вот эти два значения, то мы получим вот такую вот область.

Причем вот эта вот область пересечения посчитается у нас в два раза.

Откуда мы знаем прежний и минус первое?

Сейчас мы говорим, что, допустим, мы это знаем.

Вот я показываю, как через три значения пересчитать.

А затем я скажу, в каком порядке нам считать, чтобы мы действительно на момент подсчета препитого-житого знали все вот эти три величины, необходимые нам для подсчета.

Так вот, мы их просуммировали и получили сумму вот в таком вот прямоугольничке.

Но вот эту сумму мы посчитали два раза.

Это плохо, поэтому нам нужно ее вычесть, чтобы она считалась не два раза, а только один раз.

Ну и все.

Что мы знаем теперь?

Теперь мы знаем сумму вот таких вот элементов, ну кроме вот этого вот одного элемента.

Ну а что это за элемент?

Ну это a и t житое.

Да, какой вопрос, Федор?

Федор, вопрос есть какой-то?

А, окей, хорошо.

Сейчас понятно, как мы считаем прев и джитая, если мы знаем вот эти вот три значения.

1, 2, 3.

Пока мы не знаем, откуда мы их знаем, но вот, допустим, мы знаем три значения этих и хотим посчитать.

Всем понятно?

Хорошо, мы будем считать, что да.

А теперь давайте заметим, что можно пересчитывать ижи вот в таком порядке.

Сейчас.

Мы считаем все единицы, потому что мы ровно как и в случае с одномерным массивом заполним вот этот массив префиксных сумм, двумерный массив, вот здесь вот ноликами.

Первая строка и первый столбец будут равны нулю.

Они будут нулевыми для удобства подсчета.

А здесь мы просто поставим вот эту формулку.

тогда понятно, что когда мы считаем и ты житый элемент, мы уже знаем и минус первый житый, мы знаем и g минус первый, и и минус первый g минус первый.

Таким образом, мы решили задачу.

Мы научились читать массив двумерных префиксных сумм.

Понятно?

Вопросы, может, есть?

Напишите, кому понятно, давайте напишите.

Ну хорошо, я считаю, что всем понятно.

Если вдруг возникнут вопросы, то задавайте, это важно осознать.

Итак, зачем же мы вообще посчитали такую штуку?

Ну, чтобы решать такую задачу.

Пусть дан двумерный массив А, здесь также дана какая-то табличка,

И мы хотим считать вот на таком под прямоугольнике сумму.

Есть ли у вас идеи, как такое можно считать?

Так, Федор, есть какой-то вопрос по прошлому слайду?

Если есть, я готов ответить.

Ну, короче, если будет вопрос, напишите, я отвечу.

Ну, значит, какие у вас идеи?

Как вот можно посчитать сумму в таком вот подпрямоугольничке?

Мы считаем, что у нас... Откуда мы знаем PREV и G-1?

Еще раз, сейчас, секунду.

Я говорю, мы считаем массив PREV вот в таких вот двух вложенных циклах.

Когда мы считаем ij, мы на прошлой итерации вот этого цикла, вот этого вот цикла, посчитали ij-1.

То есть мы в цикле постепенно подсчитываем prep и tj.

Как это выглядит?

Давайте покажу.

Мы сначала проходим вот так, потом вот так,

Вот так.

И когда мы хотим посчитать вот этот элемент, нам нужно знать, что вот эти вот три элемента.

Но заметим, что мы их уже знаем.

Потому что прошлую строку мы прошли раньше, а предыдущий элемент мы вот на предыдущей итерации как раз и посчитали.

Теперь стало понятнее?

Федор?

Еще раз, то есть мы в двух циклах постепенно подсчитываем массив.

Хорошо.

Ни у кого вопросов не осталось?

Это важно осознать, потому что сейчас мы перейдем... Да, это ответ на следующую задачу.

Вот конкретно по тому, как считать PREV для двумерного случая.

У кого-то остались вопросы?

Если надо изменять элементы, это намного более сложная задача.

Конечно, мы могли бы сейчас изменить элемент и заново пересчитать полностью весь массив.

Но логично, что это будет работать довольно долго.

Если мы хотим как-то быстро, там, за о от единицы, за о от логарифма, ну, вот как-то научиться изменять, это более сложная задача, которая не решается только с помощью префиксных сумм.

Для этого нужно знать более сложную структуру данных.

На лекции разбираться это не будет.

Массив разницы, чтобы решить задачу, вот,

про которую сказал Иван, массива разницы будет недостаточно.

Сейчас, если нужно изменять элементы и при этом уметь отвечать на запросы суммы, то есть если у нас есть два типа запросов, изменить элемент и сказать сумму, но под прямоугольники, такое решать тяжело.

Если нам нужно изменять элементы, только изменять, а в конце вывести получившуюся матрицу, такое мы решать умеем, и чуть позже мы это затронем.

Вот по текущему вопросу никого нет.

Вернемся к этой задаче.

Вот там в чате написали, что как задача координаты полуинтервалами сдаются.

Да, надо про это поговорить.

Смотрите, вот это Lx, вот это Rx.

Сейчас, да.

Вот это Ly, вот это Ry.

Понятно?

То есть мы отдельно задаем для одной координаты полуинтервал и для другой координаты.

И хотим уметь отвечать на вопросы.

Вот в таких терминах.

Вы же там уже написали формулу.

Давайте я ее напишу.

Давайте поймем, почему эта формула верна.

Мы хотим посчитать вот такую сумму.

Ну, давайте для начала возьмем сумму на всем.

Можем посчитать сумму на rx, rx.

Ну да, вот мы считаем и вычитаем.

Сейчас, что там написали?

Pref, y, x.

Да, вот то, что написали в чате, это действительно правильная формула.

Она эквивалентна тому, что я написал, только там x и y поменены местами.

Сейчас, да, там у тебя напутано.

Вот в формуле синтетона ты напутал немного с координатами.

Так, еще раз, почему это верно?

Мы считаем сумму на всем вот таком большом префиксном подпрямогольнике.

И затем...

Хотим вычесть вот это, потому что это лишние элементы, они не входят в наш нужный в запросе подпрямоугольник.

И хотим вычесть вот это.

Собственно, вот это мы и делаем, мы их вычли.

Но теперь по аналогии с предыдущей задачей, вот в этом вот, точнее не с задачей, а с подсчетом префиксных сумм в двумерном массиве, вот в этом подпрямоугольнике мы сумму вычли два раза.

Это неправильно, нам нужно, чтобы она вошла с коэффициентом 0, а сейчас она вошла с коэффициентом минус 1.

Но это неправильно.

Давайте ее прибавим.

Разницы нет, но смотри, у тебя перепутано.

У тебя сначала идет pref ly lx, а последний у тебя pref rx ly.

У тебя либо все первые элементы... Мы можем здесь изменить lx на ly, rx на ry, ly на... Сейчас, сори.

на Lx, а Ry на Rx.

Но не совсем получишь твоя формула, потому что смотри, вот у тебя ты написал вот так вот, плюс что-то там, и потом минус прев RxLy.

Почему это неверно?

Видишь, у тебя здесь y на первом месте стоит, а здесь x. Это неверно.

У тебя либо как бы

первым индексом должны идти иксы везде, либо игреки.

Понимаешь, почему твоя формула неверная?

Вот, да, если там изменить, то кажется, это действительно будет правда.

Просто, ну, немного ты там поменял индексы икс на игрек, это нормально.

Так, замену сотрем, как бы.

Вопросы есть?

Понятно, почему это верно?

Давайте подождем, чтобы все осознали.

То есть тут примерно как по аналогии, когда мы считали префиксные суммы в двумерном массиве, мы тоже что-то вычитаем, что-то складываем, чтобы все вошло с нужным вкладом.

Для тех, кто знает, что такое формула включения и исключений, я думаю, они могут здесь увидеть небольшие отсылки к этому, потому что мы вычитаем, а потом прибавляем пересечения.

Хорошо, идем дальше.

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

Это чуть более сложно, чуть более сложнее объяснять, но в трехмерном, четырехмерном, пятимерном, в n-мерном мы можем считать по формуле включения и исключения.

Это и считается по формуле включения-исключения.

Я, собственно, вот здесь и писал формулу включения-исключения.

Просто для случая, когда n равно 2, это как-то не совсем интересно рассматривать формулу включения-исключения.

Проще объяснить вот так.

Как называется трехмерный массив?

Лично я не знаю какого-то интересного математического названия.

Трехмерный массив так и называется.

Так, давайте перейдем к следующей теме, разностный массив.

Вот там уже его до этого упоминали.

Значит, разностный массив задается довольно легко.

Разностным массивом массива a0, a1, an-1 называется такой массив d, что d0 равен a0, а d и t равно a и t минус a и минус 1 для всех, и от единицы до n-1.

Покажу пример.

Пусть у нас был массив какой-нибудь 1, 3, 2, 5, 0, 4.

Массив D. Я также буду писать вот здесь, в промежутках.

1, 3-1, 2, 2-3, минус 1, 5-2, 3, 0-5, минус 5, 4-0, 4.

Вот, довольно легко.

Всем понятно?

Ну, думаю, да.

Отметим, что разностный массив имеет такую же длину, как и массив А, длину N. И что же в нем такого полезного и важного?

Ну, заметим, что если мы возьмем массив 1, 2, ну, вот этот вот разностный массив, давайте построим его префиксную сумму.

Что мы получим?

0, 1, 3, 2, 5.

Заметим, что вот это вот, без первонулевого элемента, это в точности массив a. То есть, если мы построим по массиву его разностный массив, и по этому разностному массиву построим массив префиксных сумм, то получим тот же массив a. Я думаю, сейчас стало понятно, почему мы d0 определили именно как a0.

Это нужно для того, чтобы по массиву разностных сумм однозначно восстановить массив a.

На разовый массив нужно выделять больше памяти, чем на массив А. Почему?

Да, сейчас еще раз свойства повторю.

Почему?

Это неправда.

У нас длина и массива А, и массива Д, N, ровно.

Больше памяти нам выделять не надо.

Какие свойства?

Разовый массив определяется так.

Первый элемент D0 равен А0.

а d it элемент – это разница a it и a-1 элемента, так как может быть переполнение типа.

Да, это правда, и в массиве префиксных сумм вы тоже должны это учитывать, там тоже может быть переполнение, но если считать асимптотически, то и там, и там у нас o от n. Переполнение может быть, конечно, но длина-то у нас одинаковая.

Асимптотически действительно у нас линейная память.

Свойства, значит, возвращаемся.

Понятно, как определяется разностный массив, Филипп?

Хорошо.

Теперь посмотрим на этот разностный массив.

Заметим, что если мы на массиве построим префиксные суммы, получим исходный массив А. Вот мы нарисовали пример, который это демонстрирует.

Почему это так?

Ну вот давайте посмотрим на эту формулу и просто попереносим слагаемые.

Получим, что a и t равно d и t плюс a и минус первое.

Ну вот теперь если a заменить на pref, а d заменить на a, то мы получим в точности формулу префиксов SUM.

Понятно, почему это правда?

Это важное свойство разностного массива, которое позволяет нам решать очень многие задачи с помощью него.

Даже там, где может быть не совсем понятно, причем тут массив префиксных сумм, вот разностный массив очень полезен.

Частностный массив, не знаю.

Так, всем понятно, что такое разностный массив и какие у него свойства?

Ну, оно вот одно важное, что если по нему построить префиксные суммы, то получим исходный массив.

Окей.

Теперь давайте перейдем к задаче.

У нас дан массив А. Давайте рассмотрим какой-нибудь частный случай, когда массив А состоит из пяти элементов.

а it изменили на pref it.

Да, ну вот здесь я показываю, что если мы на массиве d построим префиксные суммы, то вот эти вот формулы, вот эта формула, это определение разностного массива.

Почему?

Ну потому что это буквально то, что написано здесь.

Я просто перенес слагаемые.

Я перенес i-1 влево и получил вот это.

А если в задаче...

Если есть и разностный, и суммный, то рассчитать один, а дальше сложить с исходным для получения второго же быстрее.

Рассчитать разностный, а затем сложить с исходным для получения второго.

Не понимаю, почему это будет быстрее, или вычесть...

Разностный массив и префиксные суммы связаны, но при этом они все же отвечают на разные вопросы.

Когда нам нужно построить префиксные суммы, нам не нужно искусственно создавать зачем-то разностный массив.

Я не совсем понял, что ты имеешь в виду.

Если и то, и то есть, то есть ты предлагаешь взять массив А, по нему построить разностный массив D,

а затем по массиву D построить массив префиксных сумм.

Да?

Ну смотри, если ты по массиву A построишь массив D, разностный массив, а потом построишь префсуммы, то у тебя получится массив A, не массив префиксных сумм.

Это, собственно, свойство разностного массива, его нужно осознать.

Вот здесь я продемонстрировал почему.

Мы посчитали A, ну вот, точнее, A нам дан,

Посчитали массив D по нему, просто по определению.

И теперь, если мы посчитаем PREF D, вот это вот PREF D – это префиксные суммы.

Ну, вот это PREF D – это то же самое, что A. Понятно?

То есть, непонятно.

Хорошо.

Давайте попробуем объяснить не на примере, а более строго.

Если вычесть... В любом случае это будет не быстрее.

Всегда быстрее сделать пречисленный массив, чем сначала по нему строить что-то, потом по этому еще что-то.

Всегда выгоднее один раз построить массив.

Из А до Д, если вычесть, это будет не быстрее.

Кажется, это будет верно, но это точно будет не быстрее.

Если нам нужно построить и то, и то, быстрее будет построить отдельно массив префиксных сумм, отдельно построить массив разностных массив, просто два раза, два цикла написать, это будет быстрее.

Можно сказать, что он выполняет обратную функцию префиксному.

Действительно, да, это правда.

Так, теперь, вот там непонятно было в чате, давайте пытаюсь поподробнее объяснить.

Что мы знаем про...

разностный массив.

Он определяется вот так.

Это понятно?

Это просто определение.

Он имеет длину n и определяется следующим образом.

Давайте посмотрим на эту формулу.

Ее можно переписать следующим образом, что d и t плюс a и минус первое равно a и t. Тогда давайте заметим, что если нам дан массив d, то мы

По массиву D можем построить массив А, руководствуясь вот такой формулой.

И получится, что массив А – массив префиксных сумм для D. Федор, стало понятнее?

Хорошо.

Вопросов не осталось.

Сейчас важно осознать, почему это действительно так.

Если использовать один префиксный массив, а при потребности противоположном получать значение по индексу.

Не совсем понял, что ты имеешь в виду.

Попробуй по-другому сформулировать.

Я что-то не очень понял.

По потребности.

Какая потребность?

Мы можем обращаться к разницу, можем к префиксному.

Не вводить второй массив, а сразу получать значение индекса.

Подожди.

То есть ты хочешь по массиву a получать значение массива d или что?

Ну да, действительно, ты можешь рассмотреть.

У тебя d и t это по определению... Сейчас, секунду, что-то стерлось.

d и t это по определению a и t минус a и минус первое.

Тебе a it и a минус первое дано, ну, это мотив for a, ты можешь от единицы узнать d it.

Собственно, так выглядит построение.

d0 равен, сейчас, секунду, d0 равен a0.

Так же быстрее.

Короче, смотри.

Все, что мы сейчас рассматривали, и разностный массив, и массив префиксных сумм, это все работает за ООТ.

Если мы несколько раз чего-то там поделаем, быстрее не станет.

Это все еще будет асимптотически ООТ.

Поэтому...

немного бесполезно сейчас выдумывать, что вот, а если построить префиксный, потом по нему разностный, как бы вот надо запомнить одно это свойство, почему оно важно, я покажу чуть позже, что по массиву d можно построить массив префиксных сумм, и он будет равен массиву a, по которому мы исходно строили массив d. Так, сейчас читаю вопросы.

В префиксных суммах прибавляется предыдущее значение из массива, которое мы строим, а здесь из исходного.

Кирилл, ты вот про эту формулу?

Смотри, я что говорю?

В этом случае, вот в этой формуле, мы знаем массив D, а массив A не знаем.

Мы хотим его посчитать, используя D. Понятно?

То есть в данном случае массив A нам неизвестен.

Мы знаем только его разностный массив.

Как раз по разностному массиву

Разностная матрица, да, есть.

Она тоже используется в задачах, где нам нужно делать изменения на двумерном массиве, но при этом нам не нужно получать запросы.

Чуть позже я это обговорю.

Префиксный на префиксном существует, но это что-то странное, не совсем понятно, зачем это нужно.

А вот разностный массив на разностном массиве действительно полезная вещь.

Чуть позже мы убедимся, почему.

Так, Кирилл, вопросы остались?

Еще раз, мы знаем массив D, и по нему хотим построить массив A. Нет, я не понял.

Хорошо.

Сейчас объясню.

Смотри, что мы знаем.

Массив D. Он D0, D1 и так далее, D, N-1.

И мы хотим посчитать массив A. Ну,

а 0 – это d0 по определению.

Понял?

Да, все, хорошо.

Но нам в такой ситуации не приходится строить вторую матрицу, что синтетически n квадрат.

Не совсем понял, про что это.

Видимо, это про двумерный массив.

На двумерном массиве можно строить разный массив тоже.

Переходим дальше.

Но это чуть более сложно, сегодня мы это обсуждать не будем.

Это чуть более сложный материал, который на самом деле преграждается довольно редко.

Но лично я ни разу не встречал задачу, в которой нужен разностный массив на двумерной матрице.

Разностный массив в одномерном случае, конечно, нужен.

Это действительно полезно.

Сейчас мы поймем, почему.

А в двумерном случае, ну, что-то это неочевидно.

Так, нам дан массив А, и приходит кузапросов вида «Ко всем элементам прибавить число D».

И нам в конце нужно вывести массив a, который получился после всех запросов.

Давайте построим массив разности для массива a. Вот он так выглядит.

Давайте предположим, что мы захотели... Давайте здесь будет не d, а x, чтобы у нас не было путаницы с массивом d и числом.

Пусть мы захотели прибавить на полуинтервале lr, где l равно 1, а r равно 4.

Это что значит?

Что мы захотели прибавить вот на таком отрезке число x. Сейчас все тут грязно получилось.

Хорошо, давайте посмотрим, что же случилось с массивом D0.

Ну пусть у нас вместо него появился новый массив D'.

D'0, D'1, D'2, D'3, D'4.

Значит, D'0 это что?

Это A1 минус A0.

Нет, секунду, извините, это неправда вообще.

Это A0 по определению.

a0 – это d0.

То есть d'0 совпадает с d0.

Посмотрим, d'1 – это a1 минус a0.

Но у нас a1, к нему прибавилось x. То есть на самом деле здесь написано a1 плюс x минус a0.

То есть x плюс a1 минус a0.

Я просто перенес скобочки.

Так вот, a1 минус a0 – это по определению d1.

То есть получим, что d1 штрих – это x плюс d1.

Посмотрим на d2 штрих.

Это a2 минус a1, но a2 у нас заменилось на a2 плюс x минус a1 плюс x. Раскрыв скобки, x у нас взаимоуничтожится, и получится a2 минус a1.

А это в точности d1.

d2, простите.

Ну, можно заметить, что для d3' там будет аналогичная ситуация, так как у нас и к a3, и к a2 прибавился х. А вот что случилось с d4'?

Ну, у нас a4 не изменился, а вот к a3 прибавилось х. Тогда это что?

a4 минус a3 минус х.

где a4 минус a3 это d4, которая вот из старого массива, минус x. Ну давайте заметим, что если бы у нас дальше был элемент a5 и d5, то d5 не изменилось бы, потому что и a4 и a5 никаким образом у нас тоже не изменились.

К ним никакого прибавления не случилось, значит и их разница никак не изменилась.

То есть заметим, что у нас изменилось только два значения.

d1 штрих.

и D4'.

Причем D1' это D1 плюс x, а D4' это D4 минус x. А все остальные D' и t равно D и t. При неравном 1 и неравном 4.

Понятно, что сейчас произошло?

То есть,

Что мы сделали?

Мы сказали, что если мы на полуинтервале 1, 4 прибавим число x, то в разностном массиве у нас изменятся только два элемента.

Это d1 и d4.

Давайте я побольше людей подожду.

Кирилл, непонятно, хорошо.

Что вот именно непонятно?

С какого момента объяснить?

Кирилл, вопрос.

Вот с какого момента непонятно?

Понятно, какие запросы?

С того, где доказывается, почему только два элемента D изменились.

Хорошо.

Смотри, давай посмотрим на элемент D0.

Вот элемент D0 – это элемент A0.

Элемент A0 у нас изменился?

Нет, не изменился.

Поэтому D0 тоже не изменится.

Согласен?

Хорошо.

Посмотрим на элемент D1.

Что такое D1?

D1 по определению – это разность А1 и А0.

А0 у нас никак не изменилась.

А А1 увеличился на х. Почему?

Потому что у нас был такой запрос.

А1 нужно было увеличить на х. То есть стало А1 плюс х минус А0.

Но тут просто перенесем скобочки вот таким образом.

А вот это вот у нас – это D1.

Понятно, почему d1' – это x плюс d1.

Еще раз, d' – это новый разностный массив, который получился, а d – это старый, который был до выполнения запроса.

Хорошо.

Посмотрим на элемент d2.

Элемент d2 отвечает за разность элементов a2 и a1, но они оба у нас увеличились на x, а значит, их разница никак не изменилась.

У нас и к тому прибавилось x. Разница никак не меняется.

Понятно, Кирилл, почему D2 и D3 не изменятся?

Хорошо.

С D4 аналогичная ситуация, как с D1.

Сейчас я прочитаю, что там пишут в чате.

Сейчас мы с Кириллом разберемся.

D4 изменяется точно по той же причине, потому что у нас A3 увеличилась на х, а A4 не изменилась.

То есть разница у них должна уменьшиться на х.

Так как вот было a4 минус a3.

Сейчас, место закончилось.

Было a4 минус a3, а стало a4 минус a3 плюс x. Вот.

Кирилл, стало понятно, почему?

Все, то есть вопросов больше нет, да?

Сейчас я отвечу на вопросы в чате.

Все, хорошо.

Значит, у нас a и t равно prev d и t. Действительно, если мы хотим добавлять плюс x к какому-то отрезку, то мы добавляем плюс x к его первому элементу, плюс x, тем самым увеличиваем все их приехостные суммы, и так как у нас после этого отрезка не добавляется плюс x, мы отнимаем минус x. Да, Филипп, ты действительно правильно написал.

Нам про это и так надо думать.

Да, это правда.

А оно не изменилось, потому что l равно 1 или как?

Да, потому что если бы... Ну вот, l равно 1, оно не затрагивает нулевой элемент.

То есть a0 у нас не изменился.

У нас 0 индексация, то есть мы считаем, что элементы массива нумеруются с нуля.

А потом прибавляем к этому предсумму.

Сейчас обсудим.

Для этой задачи sparse table не подойдет.

Sparse table нет.

Sparse table вообще про другое.

Sparse table у нас считает минимум и максимум на отрезках.

Он не умеет прибавлять ничего, по крайней мере классический sparse table.

И в таком случае нет, мы такое делать не умеем.

Спортстейбл здесь не подойдет.

Вообще никак.

Да, вот как здесь правильно написали в чате, что мы теперь получили.

Получили массив D. Но нам-то нужно вывести массив A, а мы говорим, что мы по массиву D умеем получать массив A, просто построив пресс-фуму.

Таким образом, что у нас было?

Вот концепция решения.

Дан массив А. Мы по нему строим D. Делаем операции на D. И в конце по D строим превсуммы.

И благодаря этому получаем массив А.

Вопросы есть какие-то?

Понятно?

Концепция решения?

Если есть, задавайте вопросы.

Сейчас мы перейдем к интересной возможности сделать дерево отрезков на матрице.

Да, это называется двумерное дерево отрезков.

И это довольно сложный алгоритм.

Конечно, мы сегодня его обсуждать не будем.

Но да, дерево отрезков можно сделать на матрице.

А симптотик всего решения выходит 3n.

Все-таки в симптотике мы обычно убираем константы.

Поэтому асимптотика всего решения от n, потому что на запрос мы отвечаем за от единицы.

Дан а – это просто считать его, построить массив d от n, делать запросы от единицы, и под d построить превсумы – это от n. Я так и не понял прикол асимптотики.

Если говорить не сугубо математическим языком, а вот объяснять просто, асимптотика – это…

Как у нас растет?

Ну, типа, да, вот это как растет количество действий.

То есть, смотри, если мы делаем 10n операций, то при достаточно больших n это будет то же самое, что и n, понимаешь?

Ну, смотри, давай возьмем не 10, а допустим 2n.

Согласись, для программы не очень важно, типа, 10 в 18 операции мы сделаем.

Ну, конечно, это очень много, давайте не 10 в 18, а 10 в 8.

Сколько мы сделаем операций?

10 в 8 или 2 на 10 в 8?

Потому что это очень близкие числа.

Ты можешь просто взять два компьютера условно и параллельно на них запустить эту программу.

Поэтому это будет плюс-минус одно и то же с точки зрения программы.

Все это будет O от N.

А вот как бы от n, n и n квадрат у тебя отличаются достаточно сильно.

Почему?

Потому что, ну да, 10 в квадрате и 10 в четвертой отличаются мало.

Но вот 10 в сотой и 10 в двухсотой – это очень разные числа, и мы не можем просто опустить этот квадрат.

Так, о чем тогда вопрос?

Прикол асимптотики в том, что она позволяет нам оценить, как быстро работает наша программа.

Если наша программа состоит из большого... Просто если контакт сообщается... Действительно, именно поэтому мы не можем асимптотику... Считать, что асимптотика полностью описывает наш алгоритм.

Константы очень важно учитывать.

Именно поэтому, например, anorderedMap не работает за от единицы.

Он работает за от константы.

И эта константа, anorderedMap, anorderedSet,

И вот эта константа может быть непонятно какой.

То есть вы не можете говорить, что у вас одна операция выполняется при обращении к аннордер-циту.

Выполняется константное количество операций.

Асимптотика помогает понять, что происходит.

Хуже n квадрат?

Ну, это неправда.

Смотри, возьми n 10 в сотой.

Тогда у тебя n квадрат будет хуже, чем то, что ты написал 10 миллионов на n.

Понимаешь?

Мы не можем это оценить, потому что при разных n, то есть можно взять достаточно большой n, вот да, смотря какие ходы и данные.

Собственно, про это асимптотика говорит.

Так, хорошо, если вопросов нет, давайте перейдем дальше.

Код решения задачи показать?

Ну, давайте, хорошо.

Покажем сейчас.

Так, все вроде видно должно быть.

Ну, значит, нам был дан массив А. Мы по нему считаем массив D. Напишем ланги, ну, неважно.

Просто по определению его строим.

И у нас есть q-запросов.

Вопросов нет пока.

То есть константно важна, но за счет ее можно принимать речь.

Да, действительно.

Константно важна, чтобы понимать, сколько реально будет ваша программа работать, а асимптотика важна, чтобы понимать в общем случае, что будет происходить.

Нам даны два числа, lr и число x, которое мы хотим прибавить.

Значит, считаем, что у нас уже дан полуинтервал в 0 индексации.

Тогда что у нас там было?

Ну, в общем, напомню, у нас там был интервал 1,4, и мы сказали, что изменилось у нас d1, то есть dl у нас увеличилось на x, а dr уменьшилось на x. Да, кстати, остался один важный момент.

Я учусь в университете, но не в СУ, а в высшей школе экономики.

Вот скажите, допустим, нам пришел запрос 0n.

В 0 индексации такое возможно, действительно.

Это ко всем элементам прибавить какое-то число.

Скажите, будет ли работать данная программа?

Вот конкретно такой код, который я написал.

Что такое l?

l – это левая граница.

Мы прибавляем на отрезке, точнее, на полуинтервале.

У нас есть полуинтервал l, r. d размера n. Действительно.

Вот тут у нас будет выход за границу.

Это плохо.

Поэтому здесь нужно сделать такой if.

Давайте поймем, какой в этом смысл...

с точки зрения объяснения, не программный, а вот где же была ошибка в наших рассуждениях.

Давайте вернемся сейчас.

Давайте так, по коду есть вопросы?

Да, скажу, что ошибка была, когда у нас был вот такой код.

Когда мы изменяем последний элемент, то есть когда r равно n, то есть когда мы n минус первый элемент изменяем тоже,

то после него никакого элемента нет.

А значит, нам не на что, нет такой разницы, которую мы хотим изменить.

Поэтому нам и не нужно рассматривать этот элемент.

Так, то есть вопросов нет, да?

Да, сейчас.

Это неправда, смотри.

Если r равно n, то ты обращаешься в данном случае к элементу dn, понимаешь?

Это плохо.

У тебя массив D размера N. Это будет выход за границу.

В питоне у тебя будет... Программа упадет, а в C++ у тебя может случиться все что угодно.

Она может упасть, дать неверный ответ.

Это называется undefining behavior.

Неопределенное поведение.

За границу выходить нельзя.

Нужно самим следить, чтобы такого не допускалось.

Филипп, понятно, почему то, что ты написал, это не совсем правда?

Хорошо.

Какие-то вопросы по реализации, по данной задаче есть?

Сейчас мы перейдем к другой.

Ну, терминальный оператор иногда бывает удобный, конечно.

Но я считаю, что вопросов нет, если никто не задает.

Вот, можете написать, отвечу.

Возвращаемся.

У нас осталась одна последняя задача.

Сейчас, да.

Да, натив А, как и в прошлой задаче.

И мы хотим к элементам на полуинтервале прибавить арифметическую прогрессию.

То есть на каком-то полуинтервале мы хотим… Давайте рассмотрим пример.

Допустим, на полуинтервале 1,4 мы хотим прибавить арифметическую прогрессию, где х равно 2.

Тогда как у нас массив будет выглядеть?

А0, а1 плюс х, а2 плюс…

2х, а3 плюс 3х, а4.

Ну, это все знают, да, но чтобы понять, что именно тут полный формат, а не отрезки, вот.

Как решать такую задачу?

Давайте рассмотрим разностный массив.

Смон будет равен.

Мы рассмотрим вот в данном случае.

До этого был... Сейчас.

До этого был d0,

d1, d2, d3, d4.

Что теперь произойдет с разным массивом?

d0 у нас не изменится.

Здесь у нас станет d1 плюс x. Здесь будет d2 плюс x. Здесь будет d3 плюс x. Здесь будет d4 минус 3x, кажется.

Да.

Понятно, почему разовый массив будет выглядеть именно так?

Тут, собственно, то же самое, что в предыдущей задаче.

Ну, то есть аналогично.

Хорошо, понятно.

Ну, а тогда смотрите, что же у нас случилось.

У нас на каком-то отрезке прибавилось число x в разовом массиве.

И какой-то один элементик, там у нас вышлось одно число.

Поэтому давайте построим разностный массив разностного массива.

И как в прошлой сдаче, на разностном массиве сделаем прибавление на отрезки.

Ну и просто сделаем вычитание в одном элементе.

Таким образом, получим разностный массив разностного массива.

Выполним все запросы за от единицы на этом разностном массиве разностного массива.

а затем два раза построим предсуммы, таким образом вернувшись к массиву А. Код мы писать не будем, потому что, во-первых, у нас уже время заканчивается, а во-вторых, там, в принципе, будет примерно так же, как в прошлой задаче, просто вот мы будем делать прибавление не на самом массиве А, а на массиве разностном.

Вопросы есть по этой задаче?

Так, Александр, это значит, что вопросов нет или непонятно?

Хорошо.

Тогда давайте так.

Есть ли какие-то, как понять, когда использовать префиксный массив, а когда разность?

Ну, смотри.

Вот можно заметить одну концепцию в нашем занятии.

Когда мы рассматривали задачу, где нужно находить сумму или какую-то функцию на отрезке, то есть нужно выводить какой-то ответ, а не изменять что-то, в этом случае мы использовали префиксный массив.

А в том случае, когда нам нужно что-то изменять и ничего не вводить до конца, а в конце вывести просто результат выполнения всех запросов, когда нам нужно что-то изменять, тогда в этом случае разностный массив будет действительно удобнее.

Ну а так, я думаю, у вас будет возможность практиковаться на контесте.

Там у задачки разного уровня.

Сейчас про контест еще скажу.

Вопросы есть какие-то?

Анотация воздействия на квадрат – это же ОТН.

Ну, нет, ОТН и ОТН квадрат – разные вещи все же.

Так, давайте так, всем все понятно?

Хорошо.

Теперь скажу пару слов про контест.

В контесте будет пять задач.

Все они будут формата муниципального этапа.

Что это значит?

Что в каждой вы можете набрать частичные баллы за частичные решения.

То есть во всех задачах вы можете не писать полное решение, а написать, допустим, решение, которое работает более медленно, или работает не на всех тестах, а в каких-то только частных случаях, и тогда вы получите частичные баллы.

Что же написать на частичные баллы, вот что именно нужно писать, вы увидите в условиях к задачам.

Я настоятельно рекомендую прочитать вам все задачи.

и прочитать все подзадачи в карте задачи.

То есть по каждой задаче вы сможете набрать какие-то частичные баллы, написать просто решение в лоб без даже использования материала лекции.

Поверьте, этот навык довольно полезный на муниципе, регионе, в серосе, вообще на всех олимпиадах с частичными баллами.

Поэтому желаю удачи, желаю прочитать все задачи и все подзадачи.

Вот.

Задавайте вопросы в чате, я буду стараться отвечать.

Так, что здесь написано?

Я написал код, сложненый, цзн, пока комбинатурка, все работает, пока не беру остатка деления на m. Давай ты напишешь это в чат сборов, и я тебе отвечу позже, потому что лекция уже закончена.

По предсказуемым суммам, если у кого-то есть вопросы, задавайте.

В девятом классе результат по баллам как берется?

Честно говоря, это зависит от региона.

Я бы советовал перед Олимпиадой прочитать регламент, как там начисляются баллы, посмотреть, что было в предыдущие годы.

Скинуть ссылку на чат?

Сейчас скину, да.

Всем до свидания, ребят.

Куда написать?

В чат сборов.

Сейчас скину ссылку.

Сейчас, секунду.

Вот.

Она привязана к каналу.

Задавайте вопросы, я буду стараться отвечать.

Решайте контест.

Всем удачи, всем спасибо за то, что пришли, послушали.

До свидания, всем удачи на муниципе.