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

Как две отметки задают прибавку на целом диапазоне

Восстанавливаем изменения по разностям, прибавляем значение на включённом диапазоне и объясняем отменяющую отметку сразу после его конца.

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

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

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

Разностный массив хранит изменение между соседними значениями. Чтобы прибавить x ко всем элементам включённого диапазона [l,r], достаточно добавить x в разность на позиции l и вычесть x на позиции r+1. Сами значения затем восстанавливаются накоплением разностей.

Две отметки вместо множества исправлений

Есть пять ящиков с исходными количествами [2,2,2,2,2]. Номера ящиков начинаются с единицы. Нужно добавить по 3 предмета в ящики со второго по четвёртый. Вместо немедленного изменения трёх клеток запишем начало добавки на позиции 2 и её отмену на позиции 5.

При проходе слева направо текущая добавка до позиции 2 равна нулю, затем становится 3 и сохраняется через позиции 3 и 4. На позиции 5 отметка −3 возвращает её к нулю. Поэтому результат равен [2,5,5,5,2]. Отменять добавку на позиции 4 было бы рано: последний ящик диапазона тоже должен измениться.

Пример

События добавки: позиция 2 — плюс 3, позиция 5 — минус 3.

Накопленные добавки равны [0,3,3,3,0]. Их можно прибавить к исходному массиву после обработки всех событий.

Полные разности и отдельные добавки

Можно хранить разности самого исходного массива: D(1)=A(1), а дальше D(i)=A(i)−A(i−1). Для [2,2,2,2,2] это [2,0,0,0,0]. После двух отметок получится [2,3,0,0,−3]. Накопление даёт тот же ответ [2,5,5,5,2].

Другая схема — сначала обнулить отдельный массив изменений, а после накопления сложить его с исходными значениями. Эти варианты не следует смешивать: если разности уже включают исходное содержимое, повторное прибавление исходного массива удвоит его. Подпишите смысл каждой рабочей таблицы до вычисления.

Перекрытия складываются, но результат ещё не готов

Если затем убрать по одному предмету из ящиков 3…5, добавляем событие −1 на позиции 3 и +1 на позиции 6. После обеих операций результат равен [2,5,4,4,1]. Позиция 6 служебная: она находится сразу за последним ящиком и позволяет одинаково записывать правую границу.

При q прибавлениях и одном итоговом восстановлении достаточно порядка q+n действий. Но отдельная разность не равна текущему содержимому соответствующего ящика: для чтения значения нужна накопленная сумма. Если после каждой операции требуется много произвольных запросов, простая отложенная схема может оказаться неудобной и понадобится динамическая структура. Служебную позицию за концом массива выделяют заранее и не показывают как дополнительный ящик. Она нужна для единого правила записи событий, но не входит в итоговые пользовательские данные.

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

А теперь — вы

Массив длины 6 индексируется с единицы. Где отменить прибавку +4 к включённому диапазону [2,5]?

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

Работает ли это для отрицательной прибавки?

Да: начало получает отрицательное число, а отметка после конца — противоположное положительное. Это описывает уменьшение значений на диапазоне.

Можно ли теми же отметками присвоить диапазону число 7?

Обычные разности так представляют прибавления. Присваивание зависит от прежних значений и не заменяется двумя независимыми событиями +7 и −7.

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

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

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