Как узнать
сумма непрерывного отрезка: сколько подмассивов дают k, много вопросов о сумме от i до j или отрицательные числа, из-за которых не работает скользящее окно.
Как решать такие задачи
- Перепиши сумму отрезка как разность двух накопленных сумм.
- Реши, что помнить о прошлых префиксах: сколько раз встречался, первый индекс или только сам факт.
- Сначала положи в словарь пустой префикс 0, чтобы считались и отрезки от начала.
- Для каждого числа: обнови сумму, поищи нужный префикс, потом сохрани текущий.
Вариант: С двух сторон
То же, но накапливаем с двух сторон: один проход слева, другой справа. Подходит, когда ответ для позиции зависит от всего, что слева от неё, и всего, что справа.
- Подходит, когда ответ для i зависит от всего, что левее i, и от всего, что правее.
- Пройди слева и сохрани для каждого индекса то, что перед ним: произведение, сумму, максимум.
- Пройди справа с одной накопленной величиной для того, что после него, и объедини с сохранённым.
- Те же два прохода дают самую высокую стенку слева и справа от каждой клетки, когда считаешь, сколько дождевой воды задержится, и решают правило с двумя соседями: раздать конфеты так, чтобы рейтинг выше давал больше, чем у обоих соседей.
Где встречается
- Поиск лиц на фото. Детектор Виолы — Джонса, который есть в OpenCV, много раз считает сумму яркости в прямоугольниках. Для этого он заранее строит таблицу накопленных сумм, и сумма любого прямоугольника берётся из четырёх её чисел.
- Сортировка на видеокарте. Radix sort считает, сколько чисел попало в каждую корзину, а накопленные суммы этих счётчиков говорят, с какого места писать каждую корзину. Так сортирует библиотека CUB от NVIDIA.
- SQL. Оконная функция SUM(...) OVER (ORDER BY ...) считает нарастающий итог: для каждой строки сумму всех строк до неё. Это и есть накопленные суммы.