Информатика · объяснение и практика

Как обновить сумму окна, не пересчитывая все элементы

Вычисляем суммы последовательных окон фиксированной длины, выводим обновление через уходящий и новый элементы и проверяем количество окон.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Структуры данных · Учебная карта

Главная мысль

Если окно фиксированной длины сдвинуть на одну позицию, из него уйдёт один элемент и придёт один новый. Поэтому новую сумму получают из прежней вычитанием уходящего и прибавлением входящего значения, без повторного сложения всего окна.

Покажите, что остаётся внутри

Станция записала пять измерений [5,−2,7,1,4]. Требуется сумма каждого окна длины три. Первое окно содержит 5, −2 и 7, его сумма равна 10. После сдвига исчезает 5, остаются −2 и 7, приходит 1. Новая сумма равна 10−5+1=6.

При следующем сдвиге уходит −2 и приходит 4. Получаем 6−(−2)+4=12. Отрицательное уходящее значение именно вычитают, поэтому сумма от его удаления возрастает. Подстановка «всегда уменьшить на модуль уходящего» здесь ошибочна: операция должна соответствовать исходному знаку измерения.

Пример

Окна длины три дают суммы 10, 6 и 12.

Общие внутренние элементы уже включены в старую сумму. Они не меняются при сдвиге и потому не требуют повторной обработки.

Начальное окно и правый индекс

Для массива длины n и окна длины k при 1≤k≤n существует n−k+1 окон. При нулевой индексации первое занимает полуинтервал [0,k), следующее — [1,k+1). На шаге с новым правым индексом r уходит элемент r−k, а входит элемент r.

Начальную сумму складывают отдельно: обновление по двум элементам требует уже готового предыдущего значения. Если k=n, есть только одно окно, сдвигов нет. Если k больше длины массива, полных окон нет; нельзя молча считать отсутствующие значения нулями, если дополнение нулями не оговорено самим условием.

Что можно обновлять столь же просто

Сумма допускает удаление старого вклада обратной операцией. Среднее фиксированного окна затем получается делением суммы на k. Для минимума аналогичное вычитание невозможно: если ушёл самый маленький элемент, оставшийся минимум ещё нужно узнать. Поэтому быстрый минимум окна использует другую структуру, например монотонную очередь.

Эта статья рассматривает фиксированную длину. В задачах с переменными границами и ограничением суммы направление движения может требовать неотрицательных элементов; наш расчёт фиксированного окна такого ограничения не имеет. При дробных измерениях многократные обновления способны накапливать погрешность округления. Проверка нескольких окон прямым суммированием помогает отделить ошибку индекса от численной неточности и неверного исходного измерения.

От чтения к действию

А теперь — вы

У окна из [2,5,−1] сумма равна 6. Оно сдвигается: уходит 2, приходит 8. Какова новая сумма?

Частые вопросы

Нужно ли сортировать измерения перед сдвигом?

Нет: окна определены соседством в исходном порядке. Сортировка превратит их в другие наборы и изменит задачу.

Можно ли хранить только текущую сумму при потоковом вводе?

Нужно ещё знать уходящий элемент. Для этого сохраняют последние k значений, например в кольцевом буфере; одной суммы недостаточно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться