Префиксные суммы на Python: как решать + 12 задач с проверкой

Префиксные суммы — это «накопленные итоги» по массиву: сколько получилось, если сложить первые 1, 2, 3… элементов. В олимпиадных задачах они всплывают в сюжетах про баланс (прибыль/штраф), очки по серии действий, дневник дежурств, нагрузки по дням и любые вопросы «сколько на отрезке».

Как распознать задачу

Чаще всего в условии есть один из признаков:

• нужно много раз находить сумму на подотрезке [l..r] или сравнивать суммы разных отрезков;
• просят посчитать количество непрерывных отрезков с суммой K (как в задачах про комбо-удары), иногда при этом встречаются отрицательные числа;
• встречаются фразы «сумма на участке/квартале/за период», «точка равновесия», «сколько раз повторилась сумма».

Суть приёма

Строим массив pref, где pref[i] — сумма первых i элементов. Тогда сумма на отрезке [l..r] считается как pref[r] - pref[l-1] за O(1). Это ускоряет решения: вместо перебора всех сумм внутри отрезка мы сводим задачу к разности двух префиксов, а в задачах «сколько отрезков с суммой K» — к подсчёту, сколько раз встречалось значение pref[r] - K (обычно через словарь/хеш-таблицу) за O(N).

С чего начать

• потренируйся строить pref и проверять формулу суммы отрезка;
• реши задачи на суммы по отрезкам с несколькими запросами;
• отдельно разберись с подсчётом отрезков на сумму K через частоты префиксов;
• следи за типами: суммы могут не влезать в 32-bit, часто нужен 64-bit (long long).

Ниже — задачи с автопроверкой и разбором подхода.