Поднять весь диапазон, не трогая каждую ячейку

У тебя календарь бронирований. В начале у каждого дня ноль гостей. Одна бронь занимает дни с 3-го по 9-й на 4 гостей, и ты прибавляешь 4 к каждому из этих семи дней. Другая бронь занимает дни со 2-го по 20-й на 2 гостей, и ты прибавляешь 2 к девятнадцати дням. И так тысячи броней.

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

Итоговые числа по дням ты читаешь только один раз, в конце. До этого ты просто накладываешь прибавления по диапазонам друг на друга. Есть способ записать каждое такое прибавление двумя пометками, а потом за один проход превратить все пометки в итоговые числа.

Возьми 5 дней, с 0-го по 4-й, и бронь «+2 гостя на дни с 1-го по 3-й». Вместо трёх прибавлений ты оставляешь две пометки. В день 1 пишешь «+2»: отсюда гостей стало на 2 больше. В день 4, сразу после конца брони, пишешь «-2»: отсюда эти гости ушли.

Таких пар пометок можно поставить сколько угодно, для любых броней. В самом конце ты один раз проходишь дни с начала и ведёшь итог всех встреченных пометок. День 0: 0. Дни 1, 2, 3: по 2. День 4: снова 0. Две пометки на бронь и один проход в конце.

Заведи вспомогательный массив diff на одну ячейку длиннее данных, заполненный нулями. Чтобы прибавить val на диапазоне [l, r], поставь две пометки: diff[l] += val и diff[r+1] -= val. Пометка +val включает прибавку начиная с l. Пометка -val выключает её сразу после r.

На одно обновление больше ничего не нужно. Две записи при любой ширине диапазона.

Чтобы получить настоящие значения, пройди слева направо и веди накопленную сумму: running += diff[i], затем result[i] = running. Накопленная сумма несёт каждое +val вперёд от места, где оно включилось, и теряет его в r+1. Поэтому прибавку получают ровно дни с l по r.

Вычитай в r+1, а не в r. Прибавка должна действовать по день r включительно, поэтому выключается она на одну ячейку дальше. Если выключить её в r, последний день каждого диапазона недополучит прибавку.

Проследим на n = 5 с обновлениями [[1,3,2], [2,4,1]].

• Обновление [1,3,2]: diff[1] += 2, diff[4] -= 2.
• Обновление [2,4,1]: diff[2] += 1, diff[5] -= 1.
• Теперь diff = [0, 2, 1, 0, -2, -1].
• Накопленная сумма: 0, потом 0 + 2 = 2, потом 2 + 1 = 3, потом 3 + 0 = 3, потом 3 - 2 = 1. Значит, result = [0, 2, 3, 3, 1].

Проверь вручную: +2 на дни с 1-го по 3-й и +1 на дни со 2-го по 4-й дают ровно это.

Каждое обновление это две записи: O(1). Для u обновлений выходит O(u). Последний проход обходит каждую ячейку один раз: O(n). Всего O(n + u). Память O(n) на массив diff.

Если прибавлять к каждому элементу вручную, это O(n) на обновление и O(n·u) всего. Пометки на двух краях убирают этот множитель.

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

Занятость мест и дней в календаре с проверкой вместимости, поиск перебронирования рейсов и отелей. Применение множества правил вида «прибавить N на этом диапазоне IP-адресов» или «поднять цены в этом ценовом диапазоне», после которых результат читают один раз. Тепловая карта, на которую наносят тысячи диапазонов, а потом один раз рисуют. Везде, где сначала накапливается пачка прибавлений по диапазонам, а итоги смотрят потом.