Сигнал задачи
Когда применять
Ответ можно накопить за один проход.
Что держать в голове
- Уметь поддерживать несколько агрегатов одним линейным проходом.
- Уметь формулировать инвариант обработанного префикса.
Сложность
- Один проход по n элементам: O(n) времени; дополнительная память O(1), если состояние имеет постоянный размер.
Границы и ошибки
- Состояние префикса должно обновляться за O(1); пересчёт уже пройденной части превращает решение в O(n²).