Difference array — это почти обратная идея к prefix sum.
Если prefix sum отвечает на вопрос:
«Какая накопленная сумма получилась к этому месту?»
то difference array отвечает на вопрос:
«Что изменилось в этой точке по сравнению с предыдущей?»
То есть мы храним не сами значения массива, а разницы между соседними элементами.
Есть массив:
a = [3, 4, 8, 10, 15]
Difference array будет:
diff = [3, 1, 4, 2, 5]
Почему?
diff[0] = a[0] = 3
diff[1] = a[1] - a[0] = 4 - 3 = 1
diff[2] = a[2] - a[1] = 8 - 4 = 4
diff[3] = a[3] - a[2] = 10 - 8 = 2
diff[4] = a[4] - a[3] = 15 - 10 = 5
И вот тут видно красивую связку:
a = [3, 4, 8, 10, 15]
diff = [3, 1, 4, 2, 5]
А если теперь взять prefix sum от diff, мы восстановим исходный массив:
3
3 + 1 = 4
3 + 1 + 4 = 8
3 + 1 + 4 + 2 = 10
3 + 1 + 4 + 2 + 5 = 15
То есть:
prefix sum от difference array = исходный массив
И наоборот:
difference array от массива = разницы между соседними элементами
2. Зачем это нужно
Главная сила difference array — быстро делать массовые прибавления на отрезках.
Например, есть массив:
a = [0, 0, 0, 0, 0]
Нужно прибавить +10 ко всем элементам с индекса 1 по индекс 3:
a = [0, 10, 10, 10, 0]
Обычным способом надо пройти по отрезку:
for (let i = 1; i <= 3; i++) {
a[i] += 10;
}
Это O(length of range).
Если таких операций много, становится дорого.
А через difference array можно сделать обновление отрезка за O(1).
3. Главный трюк difference array
Допустим, мы хотим прибавить x на отрезке [l, r].
Тогда в diff делаем:
diff[l] += x
diff[r + 1] -= x
Если r + 1 выходит за границу массива, вторую операцию не делаем.
Вот это весь фокус.
Почему так?
Потому что diff[l] += x означает:
начиная с позиции
l, все последующие элементы после восстановления через prefix sum станут больше наx.
А diff[r + 1] -= x означает:
начиная с позиции
r + 1, этот эффект надо отменить.
То есть мы не меняем каждый элемент внутри отрезка.
Мы ставим две «метки»:
здесь прибавка начинается
здесь прибавка заканчивается
4. Пример пошагово
Есть массив длины 5:
a = [0, 0, 0, 0, 0]
Создаём diff длины n + 1, чтобы безопасно делать r + 1:
diff = [0, 0, 0, 0, 0, 0]
Теперь операция:
add +10 to range [1, 3]
Делаем:
diff[1] += 10
diff[4] -= 10
Получается:
diff = [0, 10, 0, 0, -10, 0]
Теперь восстанавливаем массив через prefix sum:
current = 0
i = 0: current += 0 => 0
i = 1: current += 10 => 10
i = 2: current += 0 => 10
i = 3: current += 0 => 10
i = 4: current += -10 => 0
Итог:
a = [0, 10, 10, 10, 0]
То есть сработало ровно как надо.
5. Несколько обновлений
Вот где difference array раскрывается сильнее.
Допустим, есть массив из 6 нулей:
a = [0, 0, 0, 0, 0, 0]
Нужно выполнить три операции:
+5 на [1, 3]
+2 на [2, 5]
+7 на [0, 2]
Создаём:
diff = [0, 0, 0, 0, 0, 0, 0]
Операция 1
+5 на [1, 3]
diff[1] += 5
diff[4] -= 5
diff = [0, 5, 0, 0, -5, 0, 0]
Операция 2
+2 на [2, 5]
diff[2] += 2
diff[6] -= 2
diff = [0, 5, 2, 0, -5, 0, -2]
Операция 3
+7 на [0, 2]
diff[0] += 7
diff[3] -= 7
diff = [7, 5, 2, -7, -5, 0, -2]
Теперь восстанавливаем исходный массив через prefix sum:
i = 0: 7
i = 1: 7 + 5 = 12
i = 2: 12 + 2 = 14
i = 3: 14 - 7 = 7
i = 4: 7 - 5 = 2
i = 5: 2 + 0 = 2
Итоговый массив:
a = [7, 12, 14, 7, 2, 2]
Проверим руками:
изначально: [0, 0, 0, 0, 0, 0]
+5 на [1, 3]:
[0, 5, 5, 5, 0, 0]
+2 на [2, 5]:
[0, 5, 7, 7, 2, 2]
+7 на [0, 2]:
[7, 12, 14, 7, 2, 2]
Совпало.
6. Код на JavaScript
const n = 6;
const diff = new Array(n + 1).fill(0);
function addRange(l, r, value) {
diff[l] += value;
if (r + 1 < diff.length) {
diff[r + 1] -= value;
}
}
addRange(1, 3, 5);
addRange(2, 5, 2);
addRange(0, 2, 7);
const result = new Array(n);
let current = 0;
for (let i = 0; i < n; i++) {
current += diff[i];
result[i] = current;
}
console.log(result); // [7, 12, 14, 7, 2, 2]
7. Если исходный массив не нулевой
Допустим, есть массив:
a = [3, 4, 8, 10, 15]
Строим diff:
const a = [3, 4, 8, 10, 15];
const n = a.length;
const diff = new Array(n + 1).fill(0);
diff[0] = a[0];
for (let i = 1; i < n; i++) {
diff[i] = a[i] - a[i - 1];
}
Получится:
diff = [3, 1, 4, 2, 5, 0]
Теперь можно делать range updates.
Например:
прибавить +10 на [1, 3]
diff[1] += 10;
diff[4] -= 10;
Было:
a = [3, 4, 8, 10, 15]
Должно стать:
a = [3, 14, 18, 20, 15]
Восстанавливаем через prefix sum:
const result = new Array(n);
let current = 0;
for (let i = 0; i < n; i++) {
current += diff[i];
result[i] = current;
}
console.log(result); // [3, 14, 18, 20, 15]
8. Разница между prefix sum и difference array
Можно так развести:
prefix sum:
быстро отвечает на запросы суммы по отрезку
difference array:
быстро применяет прибавления по отрезку
То есть:
| Структура | Что ускоряет |
|---|---|
prefix sum |
запрос суммы на отрезке |
difference array |
обновление всех элементов на отрезке |
prefix sum удобен, когда массив почти не меняется, но много запросов:
дай сумму [l, r]
дай сумму [l, r]
дай сумму [l, r]
difference array удобен, когда много массовых обновлений:
прибавь x на [l, r]
прибавь y на [l, r]
прибавь z на [l, r]
А потом один раз восстановить финальный массив.
9. Сложность
Без difference array:
каждое обновление отрезка: O(r - l + 1)
Если операций много, например m операций по массиву длины n, в худшем случае будет:
O(m * n)
С difference array:
каждое обновление отрезка: O(1)
восстановление массива: O(n)
Итого:
O(m + n)
Это огромная разница.
10. Главная интуиция
difference array — это не хранение значений.
Это хранение точек изменения режима.
Например:
с позиции 1 начинается +10
с позиции 4 заканчивается +10
То есть массив после восстановления как бы «несёт» текущее значение слева направо.
diff: [0, 10, 0, 0, -10]
current: 0 10 10 10 0
Это похоже на включение и выключение эффекта.
+10 — включили.
-10 — выключили.
11. Где это используется
Типичные задачи:
1. Много операций "прибавить число на отрезке".
2. Подсчёт количества пересечений интервалов.
3. Задачи с бронированиями, календарями, временными отрезками.
4. Нахождение максимального количества одновременных событий.
5. Обновление больших массивов без прохода по каждому элементу.
6. 2D difference array для прямоугольников на матрице.
Например, есть интервалы занятости:
[1, 3]
[2, 5]
[4, 6]
Можно через difference array посчитать, сколько активных интервалов в каждой точке.
Каждый интервал:
diff[start] += 1
diff[end + 1] -= 1
Потом prefix sum показывает количество активных интервалов в каждой позиции.
12. Самая короткая формула
Для обновления:
add value x to range [l, r]
делаем:
diff[l] += x
diff[r + 1] -= x
Потом:
a[i] = diff[0] + diff[1] + ... + diff[i]
То есть итоговый массив получается как prefix sum от diff.
Сверхкоротко:
Difference array — это массив “где изменение началось и где закончилось”.
Он позволяет не менять весь отрезок руками, а поставить две границы изменения. Потом prefix sum разворачивает эти границы обратно в настоящий массив.
