Сигнал задачи
Когда применять
Нужны суммы или счётчики многих диапазонов.
Что держать в голове
- Уметь строить префиксные суммы и счётчики с нулевым префиксом.
- Уметь отвечать на запрос полуинтервала разностью двух префиксов.
Сложность
- Построение O(n) времени и O(n) памяти; запрос суммы или счётчика полуинтервала после подготовки — O(1).
Границы и ошибки
- Массив префиксов обычно имеет n + 1 элемент; смешение [l, r) и [l, r] даёт ошибку на границе.