Задание № 17 · ЕГЭ

Разностный массив

Как хранить изменения на отрезках и быстро восстанавливать значения

2 мин чтенияСложность: Обновлено 29 сентября 2026

Разностный массив — это способ представить массив через изменения между соседними элементами. Он особенно полезен, когда нужно много раз прибавлять одно и то же число ко всем элементам некоторого отрезка.

Разностный массив

Для исходного массива \(a\) разностный массив \(d\) хранит первый элемент без изменения, а каждый следующий — разность соседних элементов: \(d_1=a_1\), \(d_i=a_i-a_{i-1}\) при \(i>1\). Чтобы восстановить элементы исходного массива, вычисляют кумулятивную сумму элементов \(d\).

Формула

\[d_1=a_1,\qquad d_i=a_i-a_{i-1}\ (i\ge 2),\qquad a_i=\sum_{j=1}^{i}d_j\]

Главное преимущество появляется при обработке отрезков. Чтобы прибавить число \(x\) ко всем элементам с индексами от \(l\) до \(r\), достаточно изменить только две границы разностного массива: \(d_l\) увеличить на \(x\), а \(d_{r+1}\) уменьшить на \(x\) (если \(r+1\) существует). После всех изменений исходные значения получают восстановлением через суффиксные суммы? Нет: здесь используется именно последовательное сложение слева направо, то есть префиксное накопление.

№

Пример

Пусть массив равен \([4,4,4,4,4]\), а нужно прибавить \(3\) к элементам с 2-го по 4-й. Его разностный массив: \([4,0,0,0,0]\). Изменяем границы: \(d_2\mathrel{+}=3\), \(d_5\mathrel{-}=3\). Получаем \([4,3,0,0,-3]\). Восстановление последовательным сложением даёт \([4,7,7,7,4]\). Операция над отрезком выполнена за \(O(1)\).

Не путайте

Разностный массив не хранит сами значения элементов, а хранит их приращения. Обработка отрезка массива с помощью разностей ускоряет обновления, но для получения конкретного значения после изменений нужно выполнить накопление от начала массива. Это отличается от суффиксных сумм, которые считают суммы справа налево.

Проверка

В разностном массиве нужно прибавить \(5\) к отрезку \([3;6]\). Какие изменения выполняют?

Главное за минуту

Главное

Разностный массив хранит изменения между соседними элементами.
Прибавление числа к отрезку выполняется изменением левой границы и позиции сразу после правой.
Исходный массив восстанавливают последовательным сложением элементов разностного массива.