Массивы разностей для обновлений диапазонов

Префиксные суммы позволяют быстро отвечать на запросы по диапазонам. Массив разностей переворачивает эту идею и позволяет быстро применять множество обновлений диапазонов. 🔁

Добавление значения к каждому элементу диапазона при многократном повторении занимает O(n) на одно обновление. Для q обновлений эта стоимость становится огромной.

Вместо изменения каждой ячейки запишите только места, где изменение начинается и заканчивается. Отметьте границы, а не середину.

Массив разностей хранит разницу между каждым элементом и предыдущим. Изменение одной разницы сдвигает весь последующий отрезок.

Чтобы прибавить v к элементам от l до r, прибавьте v в индексе l и вычтите v в индексе r + 1. Всего две правки покрывают весь диапазон.

Плюс в l включает изменение, а минус в r + 1 снова его выключает. Вместе они ограничивают обновление одним диапазоном.

Каждое обновление — это всего две записи в массив, поэтому q обновлений занимают в сумме O(q). Основная работа откладывается до конца.

После расстановки всех отметок вычислите префиксную сумму массива разностей. Этот единственный проход восстановит каждое итоговое значение.

Сделайте массив на одну ячейку длиннее, чтобы r + 1 никогда не вышел за его границы. Дополнительная защитная ячейка предотвращает ошибки индекса.

Вы тратите O(q) на отметки обновлений и ещё один проход O(n) на восстановление массива. Совокупная стоимость намного ниже наивной O(n умножить на q).

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

Вы прибавляете v к каждому элементу с индекса l по индекс r.

Теперь Вы умеете объединять обновления диапазонов с помощью массива разностей: отметьте l и r + 1, а затем один раз вычислите префиксные суммы для восстановления. Быстрые обновления, одно чтение. ✅