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

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

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

В контест вошли задачи:

• Общая сумма — https://judje.olprog.ru/problem/totalsum
• Сумма на одном отрезке — https://judje.olprog.ru/problem/rangesumone
• Запросы суммы на отрезке — https://judje.olprog.ru/problem/rangesumq
• Среднее на отрезке — https://judje.olprog.ru/problem/rangeaverage
• Количество чётных на отрезке — https://judje.olprog.ru/problem/countevenq
• Сумма элементов на чётных позициях — https://judje.olprog.ru/problem/sumevenpositions
• Максимальная сумма окна длины K — https://judje.olprog.ru/problem/maxwindowk
• Сумма на циклическом отрезке — https://judje.olprog.ru/problem/circularrange
• Разностный массив — https://judje.olprog.ru/problem/differencearray
• Первый отрицательный баланс — https://judje.olprog.ru/problem/balancefirstnegative
• Сумма подматрицы — https://judje.olprog.ru/problem/submatrixsum
• Количество подотрезков с заданной суммой — https://judje.olprog.ru/problem/countsumequal
• Количество подотрезков с суммой, делящейся на K — https://judje.olprog.ru/problem/countsumdivk
• Самый длинный подотрезок с равным числом 0 и 1 — https://judje.olprog.ru/problem/longestequal01
• Максимальная сумма подотрезка через префиксы — https://judje.olprog.ru/problem/maxsubarrayprefix

Этот контест подойдёт тем, кто хочет:

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

Во время решения полезно обращать внимание на несколько вопросов:

• что именно нужно заранее накопить;
• как выразить ответ на отрезке через два значения префикса;
• нужна ли нумерация с 0 или с 1;
• что делать с пустым префиксом;
• требуется ли отдельный префикс для чётных элементов, позиций или других признаков;
• можно ли заменить медленный перебор всех подотрезков подсчётом одинаковых префиксов.

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

Удачи в решении!

Ждём ваши результаты, вопросы и впечатления от задач.