Массив разностей

Массив разностей: как это работает?

Заведите массив нулей на одну ячейку длиннее входа. Каждая ячейка означает изменение в этой точке.

Чтобы прибавить v на отрезке от l до r, сделайте две записи. Прибавьте v в l и вычтите v в r плюс один.

Это всё обновление. Ничего между l и r не трогается.

Повторите для каждого заданного отрезка. Каждый стоит двух записей при любой ширине.

Когда обновления кончились, пройдите массив с накоплением. Тогда ячейка i хранит настоящее значение.

Сборка это один проход. Значит m обновлений на n ячейках стоят O(n + m).

1. diff = [0, 0, 0, 0, 0, 0]Пять рабочих ячеек плюс одна запасная. Всё начинается с нулей.
2. diff = [0, 2, 0, 0, -2, 0]Прибавляем 2 на отрезке с 1 по 3. Две записи, а не три.
3. diff = [3, 2, -3, 0, -2, 0]Прибавляем 3 на отрезке с 0 по 1. Снова две записи.
4. накопление = [3, 5, 2, 2, 0]Один проход с накоплением восстанавливает значения.
5. ответ = [3, 5, 2, 2, 0]Два обновления стоили четырёх записей. Ширина не имела значения.

function applyRangeUpdates(n, updates) {
    const diff = new Array(n + 1).fill(0);
    for (const [l, r, val] of updates) {
        diff[l] += val;
        diff[r + 1] -= val;
    }
    const result = new Array(n);
    let running = 0;
    for (let i = 0; i < n; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}

Массив разностей: разбор примера

Забронированные места на рейсах

У вас n рейсов и список броней. Каждая бронь добавляет места всем рейсам в диапазоне.

Верните общее число забронированных мест на каждом рейсе.

Цикл на каждую бронь стоил бы O(n) при широком диапазоне.

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

function corpFlightBookings(bookings, n) {
    const diff = new Array(n + 1).fill(0);

    for (const [first, last, seats] of bookings) {
        diff[first - 1] += seats;
        diff[last] -= seats; // one slot past the end of the range
    }

    const answer = new Array(n);
    let running = 0;

    for (let i = 0; i < n; i++) {
        running += diff[i];
        answer[i] = running;
    }

    return answer;
}

Массив разностей: когда применять?

Эти формулировки в условии ведут сюда:

• •сначала много обновлений диапазонов, затем один раз прочитать итоговый массив
• •прибавить значение к каждому элементу диапазона, повторить много раз
• •применить k приращений диапазона перед тем как отвечать на запросы
• •счётчики бронирований/интервалов по массиву

Массив разностей: с чем путают?

• Префиксные суммы (Prefix sums): Префиксные суммы читают много отрезков из неизменных данных. Здесь зеркально: много записей, одно чтение.
• Линия развёртки (подсчёт событий) (Sweep line (event counting)): Развёртка сортирует события, когда координаты огромны или разрежены. Здесь они прямо индексируют массив.
• Дерево Фенвика / дерево отрезков (Fenwick tree / segment tree): Дерево Фенвика отвечает на запросы между обновлениями. Массив разностей отвечает только после последнего.
• Скользящее окно (фиксированный размер) (Sliding window (fixed size)): Окно ведёт один отрезок постоянной ширины. Здесь отрезки разной ширины и свободно накладываются.

Массив разностей: частые ошибки

• Берут массив длиной ровно n

  Отрезок, кончающийся на последнем индексе, пишет в ячейку n. Выделяйте n плюс одну.

• Вычитают в r, а не в r плюс один

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

• Читают значение до сборки

  До финального прохода в ячейках лежат изменения, а не значения. Спрашивайте только после него.

• Пишут одиночное значение напрямую

  Один индекс это отрезок шириной один. Ему тоже нужны обе записи.

Массив разностей: задачи с собеседований

• Брони на рейсы: Каждая бронь это две записи на диапазоне рейсов.
• Прибавление на отрезке: Чистая форма приёма, без всего остального.
• Совместные поездки: Пассажиры садятся и выходят, а лимит нарушать нельзя.
• Сдвиг букв II: Каждый сдвиг покрывает диапазон позиций в строке.
• Год максимального населения: Рождение прибавляет единицу, смерть вычитает.
• Переговорные комнаты II: Начало занимает комнату, конец возвращает её.
• Сколько цветов цветёт: Каждый цветок покрывает диапазон дней.

Массив разностей: сложность по времени и памяти

O(n)

n до 1e6 и m обновлений на отрезках дают O(n + m). Обновление это две записи, сборка это один проход.