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

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

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

Чтобы прибавить 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;
}

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

def apply_range_updates(n, updates):
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l] += val
        diff[r + 1] -= val
    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        result[i] = running
    return result

function applyRangeUpdates(int $n, array $updates): array {
    $diff = array_fill(0, $n + 1, 0);
    foreach ($updates as [$l, $r, $val]) {
        $diff[$l] += $val;
        $diff[$r + 1] -= $val;
    }
    $result = array_fill(0, $n, 0);
    $running = 0;
    for ($i = 0; $i < $n; $i++) {
        $running += $diff[$i];
        $result[$i] = $running;
    }
    return $result;
}

    public static int[] applyRangeUpdates(int n, int[][] updates) {
        int[] diff = new int[n + 1];
        for (int[] u : updates) {
            diff[u[0]] += u[2];
            diff[u[1] + 1] -= u[2];
        }
        int[] result = new int[n];
        int running = 0;
        for (int i = 0; i < n; i++) {
            running += diff[i];
            result[i] = running;
        }
        return result;
    }

    public static int[] ApplyRangeUpdates(int n, int[][] updates) {
        var diff = new int[n + 1];
        foreach (var u in updates) {
            diff[u[0]] += u[2];
            diff[u[1] + 1] -= u[2];
        }
        var result = new int[n];
        int running = 0;
        for (int 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 приращений диапазона перед тем как отвечать на запросы». Решение на нём обычно укладывается в O(n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Массив разностей» чаще всего путают с этими паттернами: Префиксные суммы, Линия развёртки (подсчёт событий), Дерево Фенвика / дерево отрезков и Скользящее окно (фиксированный размер).

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

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

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

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

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

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

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

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

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

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

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

Паттерн «Массив разностей» решает такие задачи с собеседований: Брони на рейсы, Прибавление на отрезке, Совместные поездки, Сдвиг букв II, Год максимального населения, Переговорные комнаты II и Сколько цветов цветёт.

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

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

У паттерна «Массив разностей» целевая сложность O(n).

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