Префиксные суммы
Также: Prefix sums · накопленные суммы · cumulative sum · cumsum · разностный массив · difference array · интегральное изображение · summed-area table
Один проход по данным — и сумма за любой период считается одним вычитанием: осадки Алматы за любые дни из 85 лет, размытие фотографии с любым радиусом за одно и то же время. Плюс обратный приём — разностный массив, который превращает тысячи обновлений диапазонов в два сложения на каждое.
Ниже 85 лет погоды Алматы, с 1941 по 2025 год: каждый пиксель — один день, каждая строка — один год. Проведите по календарю и выделите любой период — день, лето, десятилетие. Сумма осадков или средняя температура появится сразу, хотя в периоде могут быть тысячи дней. Программа не складывает эти дни: она один раз заранее посчитала накопленные суммы, и теперь любой ответ — это одно вычитание.
Ползунок под календарём ищет самые дождливые k дней подряд среди всех 31 тысячи окон. По этим данным самые дождливые тридцать дней — с 28 апреля по 27 мая 1962 года, почти 291 мм: больше, чем в среднем выпадает за четыре месяца. На каждое окно уходит одно вычитание, на все — один проход.
Идея
Посчитаем P[i] — сумму первых i элементов, P[0] = 0. Тогда сумма элементов с l-го по r-й (с единицы) равна P[r] − P[l − 1]: из суммы до конца отрезка вычитаем сумму до его начала. Построение — один проход, ответ — одно вычитание, сколько бы элементов ни было в отрезке.
$$P[i] = a_1 + a_2 + \dots + a_i, \qquad a_l + \dots + a_r = P[r] - P[l - 1].$$Таблица P — это префиксные суммы. Её длина на единицу больше исходного массива: лишний нуль в начале убирает отдельный случай для отрезков, которые начинаются с первого элемента.
Средняя температура за период — та же сумма, делённая на число дней. Кстати, приём работает для любой операции, у которой есть обратная: для сложения — вычитание, для «исключающего или» — оно само. Для максимума обратной операции нет, и там нужны другие структуры: разреженная таблица или дерево отрезков.
Код
Тот же ряд, что в календаре: сумма за год, за месяц и самые дождливые 1, 7, 30 и 365 дней подряд. Для каждого окна — одно вычитание.
В Python для префиксных сумм есть itertools.accumulate, в NumPy — numpy.cumsum. Их стоит знать, но цикл из трёх строк выше делает то же самое и одинаково читается на любом языке.
Разностный массив
У префиксных сумм есть обратный приём. Пусть нужно не спрашивать суммы, а много раз прибавлять число к целому отрезку: гостиница получает тысячи броней «с ночи a по ночь b», и нужно знать, сколько номеров занято в каждую ночь. Отмечать каждую ночь каждой брони долго. Вместо этого запишем в разностный массив +1 в ночь заезда и −1 в ночь после выезда. Префиксные суммы этого массива и дают занятость: каждая бронь включается в свою первую ночь и выключается после последней.
Пять тысяч броней — десять тысяч записей вместо 34 827 отметок по ночам. Разница растёт с длиной броней: при отрезках в тысячи элементов разностный массив выигрывает в сотни и тысячи раз.
Сумма прямоугольника
Приём переносится на таблицы и картинки. Пусть S[y][x] — сумма всех пикселей выше и левее точки (x, y). Тогда сумма любого прямоугольника складывается из четырёх чисел таблицы: правый нижний угол минус два соседних плюс левый верхний, который вычли дважды.
$$\sum_{\text{прямоугольник}} = S(D) - S(B) - S(C) + S(A).$$Размытие «коробкой» заменяет каждый пиксель средним по квадрату вокруг него. Если складывать квадрат честно, работа растёт как квадрат радиуса. С таблицей сумм на каждый пиксель уходит четыре числа при любом радиусе. Подвигайте ползунок и наведите курсор на фото: видно квадрат и четыре угла, из которых берётся сумма.
В компьютерной графике такие таблицы под названием summed-area tables предложил Фрэнк Кроу в 1984 году — для сглаживания текстур. Знаменитыми их сделали Пол Виола и Майкл Джонс: в 2001 году их детектор лиц считал прямоугольные признаки через «интегральное изображение» — по четыре обращения к таблице на прямоугольник — и находил лица в видео в реальном времени.
Сколько это стоит
Построение — O(n) времени и O(n) памяти, каждый запрос — O(1). На q запросах это O(n + q) против O(n·q) у честного сложения. Для таблицы W × H — O(W·H) на построение и O(1) на прямоугольник.
Ограничение одно: данные не должны меняться. Если один элемент изменился, приходится пересчитывать все префиксные суммы после него — O(n). Когда изменения и запросы чередуются, нужны дерево Фенвика или дерево отрезков: у них и изменение, и запрос стоят O(log n).
Ещё одна тонкость — переполнение. Префиксные суммы растут вместе с n: двести тысяч чисел по миллиону — это 2·10¹¹, больше 32-битного целого. В Go берите int64, а в числах с плавающей точкой помните, что большие суммы теряют младшие разряды, и разность двух близких больших чисел может оказаться неточной.
Задачи
Первая — прямое применение на ряде осадков. Вторая сочетает префиксные суммы с хеш-таблицей: сколько периодов в истории Алматы имеют среднюю температуру ровно ноль градусов?
Сколько выпало дождя Ровно ноль градусовДанные: Погода Алматы: реанализ ERA5 (Copernicus) через Open-Meteo, CC BY 4.0 Фотографии автора сайта