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

Пусть $d_i = a_{i+1} - a_i$. Что делает с этим массивом прибавление $x$ ко всем элементам отрезка $[l, r]$?

Внутри отрезка все элементы выросли одинаково — разности не изменились. Изменились ровно две: $d_{l-1}$ выросла на $x$, $d_r$ уменьшилась на $x$.

$$\text{прибавление на отрезке} \quad \longrightarrow \quad \text{два точечных изменения.}$$

Никаких пометок, никакого проталкивания — обычное дерево с точечными изменениями.

Когда приём работает

Только если запрос тоже выражается через разности. Три примера.

Сколько соседних пар равны. Пара $(i, i+1)$ равна ровно тогда, когда $d_i = 0$. Запрос превращается в «сколько нулей в $d$ на отрезке».

Наибольшая серия подряд идущих. Условие «$a_{i+1} = a_i + 1$» — это $d_i = 1$, и вопрос сводится к самой длинной серии единиц: составной узел, который мы уже умеем.

НОД на отрезке. Здесь работает тождество

$$\gcd(a_l, a_{l+1}, \ldots, a_r) = \gcd(a_l,\ d_l,\ d_{l+1}, \ldots, d_{r-1}),$$

потому что $\gcd(x, y) = \gcd(x, y - x)$. Само $a_l$ достаётся деревом сумм по разностям, остальное — деревом НОД.

Проверено перебором: на 30 000 случайных массивов длины до 10 обе части тождества совпали.

Когда не работает

Если спрашивают сумму на отрезке, разности не помогут: сумма разностей — это не сумма элементов. Здесь работает обратный приём — дерево по префиксным суммам, где прибавление на отрезке превращается в прибавление арифметической прогрессии.

Простой частный случай: если операция — прибавление на отрезке, а спрашивают значение одного элемента, достаточно дерева сумм по разностям, и значение элемента это сумма префикса.

Границы

Единственная тонкость приёма — края, и на них ломается половина решений.

• Массив разностей на единицу короче исходного.
• Запрос про $[l, r]$ — это отрезок $[l, r-1]$ разностей, и при $l = r$ он пуст.
• Разность $d_{l-1}$ существует при $l > 1$, разность $d_r$ — при $r < n$.

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

Мысль, которую стоит унести

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