---
title: "Массив разностей"
url: https://algopath.pro/ru/patterns/difference-array
language: ru
summary: "Записывайте не значение, а изменение в каждой точке. Обновление отрезка стоит двух записей, а один проход в конце всё собирает."
updated: 2026-08-24
---

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

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

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

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

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

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

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

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

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

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

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

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

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

- **Префиксные суммы** - Префиксные суммы читают много отрезков из неизменных данных. Здесь зеркально: много записей, одно чтение.
- **Линия развёртки (подсчёт событий)** - Развёртка сортирует события, когда координаты огромны или разрежены. Здесь они прямо индексируют массив.
- **Дерево Фенвика / дерево отрезков** - Дерево Фенвика отвечает на запросы между обновлениями. Массив разностей отвечает только после последнего.
- **Скользящее окно (фиксированный размер)** - Окно ведёт один отрезок постоянной ширины. Здесь отрезки разной ширины и свободно накладываются.

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

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

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

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

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

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

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

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

```javascript
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;
}
```

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

- **Берут массив длиной ровно n** Отрезок, кончающийся на последнем индексе, пишет в ячейку n. Выделяйте n плюс одну.
- **Вычитают в r, а не в r плюс один** Правый край входит в отрезок, поэтому изменение должно его застать. Вычитайте на ячейку позже.
- **Читают значение до сборки** До финального прохода в ячейках лежат изменения, а не значения. Спрашивайте только после него.
- **Пишут одиночное значение напрямую** Один индекс это отрезок шириной один. Ему тоже нужны обе записи.

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

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

## JavaScript

```javascript
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;
}
```

## Python

```python
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
```

## PHP

```php
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;
}
```