Лекция 4. Префиксные суммы, запросы на отрезках и префиксный подход. Разностный массив

На четвёртом занятии интенсива «Быстрый старт в спортивном программировании» сначала разбираем задачи из тематического контеста к третьей теме, после чего переходим к префиксным и суффиксным суммам, запросам на отрезках, префиксному подходу и разностному массиву Подробнее в нашем Telegram-канале: https://t.me/coding_aii Вы узнаете: — как построить префиксные суммы за линейное время и отвечать на запросы суммы на отрезке за O(1); — как считать на отрезках не только суммы, но и количества, XOR и другие характеристики элементов; — как с помощью префиксных сумм считать подотрезки с нужной суммой; — когда удобнее использовать суффиксный подход и как объединять информацию слева и справа от текущей позиции; — как разностный массив позволяет выполнять массовые прибавления на отрезках за O(1) на запрос; — как совмещать несколько слоёв предобработки для подсчёта покрытий отрезками и даже прибавления арифметической прогрессии на отрезке. После просмотра лекции решайте задачи четвёртого тематического контеста, чтобы закрепить полученные знания на практике и проверить качество усвоения темы. Для этого заходите в группу на Codeforces https://codeforces.com/group/MwZqR4Zf5z как «Участник» и приступайте к решению контеста, отыскав его во вкладке «Соревнования» https://codeforces.com/group/MwZqR4Zf5z/contests Для тех, кому читать проще, чем смотреть видео, оставляю лекцию в текстовом формате https://github.com/dmkz/competitive-programming/blob/master/mirea/cources/2026-2027/aii-july/04/README.md Таймкоды: 00:00:00 Разбор задачи "A. Различные значения" 00:01:47 Разбор задачи "B. Первое и последнее вхождения" 00:05:34 Разбор задачи "C. Стек на количество уникальных элементов" 00:12:40 Разбор задачи "D. Ближайшая точка" 00:22:10 Разбор задачи "E. Менеджер памяти" 00:29:10 Начало новой темы 00:29:35 Префиксные суммы 00:38:10 Какую информацию могут хранить префиксные суммы 00:51:28 Какие функции можно считать на отрезках 00:59:25 Восстановление массива по префиксным суммам 01:01:10 Что такое префиксный подход 01:08:55 Задача "Школа танцев" 01:11:24 Что такое суффиксный подход 01:17:40 Пример задачи с Яндекс Алгоритма 01:21:00 Разностный массив 01:28:30 Покрытие точек множеством отрезков 01:33:00 Двойной шаг предподсчёта 01:35:20 Прибавление арифметической прогрессии на отрезке 01:45:35 Применение префиксных сумм к ответу для задач от L до R