Дерево отрезков

Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов $a[i],a[i+1],\dots,a[j]$ массива.

Дерево отрезков в памяти

Пусть наш массив $a$ имеет $n$ элементов: $a[0],a[1],\dots,a[n-1]$. Выберем $k$ такое, что $2^k\ge n$. Тогда для хранения дерева отрезков понадобится массив $b$ из $2^{k+1}$ элементов. В ячейке $b[2^l+u]$ при $0 \le u<2^l$ будет храниться число $f(a[u2^{k-l}], a[u2^{k-l}+1], \dots, a[(u+1)2^{k-l}-1])$, где $f$ — функция, которую мы хотим вычислять от отрезков массива. Наиболее часто в качестве $f$ берутся функции суммы, произведения, минимумы и максимумы.

Дерево отрезков с одиночной модификацией

Изменение элемента

Пусть мы изменили значение $a[i]$. Тогда нам нужно присвоить элементу $b[2^k+i]$ значение $f(a[i])$. После чего нужно обновить значения $b[2^{k-1}+i/2]$, $b[2^{k-2}+i/4]$ и.т.д. Таким образом, на добавление элемента уйдёт $O(k)=O(\log(n))$ действий.

Подсчёт функции для отрезка

Для подсчёта функции от элементов $a[l],a[l+1],\cdots,a[r-1]$ используется следующая рекурсивная процедура $\mathop{\rm count}$ от аргументов $v, L, R, l, r$. Здесь $v$ — элемент массива $b$, в котором находится значение функции для отрезка $[L;R)$, а $[l;r)\subseteq[L;R)$ — отрезок, на котором мы хотим посчитать функцию.

Если $L=l$ и $R=r$, то ответ равен $b[v]$.

Если $r\le(L+R)/2$, то ответ равен $\mathop{\rm count} (2v,L,(L+R)/2,l,r)$.

Если $l\ge(L+R)/2$, то ответ равен $\mathop{\rm count}(2v+1,(L+R)/2,R,l,r)$.

Иначе отрезок $[l,r)$ можно разбить на два отрезка: $[l,(L+R)/2)$ и $[(L+R)/2,r)$. Тогда ответом будет $f(\mathop{\rm count}(2v,L,(L+R)/2,l,(L+R)/2),\mathop{\rm count}(2v+1,(L+R)/2,R,(L+R)/2,r))$.

Таким образом, вычисление функции на отрезке $[l,r)$ сводится к вычислению функции от элементов массива $b$, соответствующих некоторым отрезкам $[2^lu;2^l(u+1))$. Можно показать, что при вычислении функции будет произведено $O(\log(n))$ рекурсивных вызовов.

Дерево отрезков с модификацией на интервале

Предположим, что мы хотим изменить значение не одной ячейки массива $a$, а целого интервала $a[l],\cdots,a[r-1]$ (например, увеличить значения всех ячеек из интервала на заданное число $X$). Тогда хранения только массива $b$ недостаточно. Однако деревья отрезков, способные вычислять сумму и максимум, можно реализовать с хранением двух массивов одинаковой длины и рекурсивной реализацией операции изменения.

Дерево отрезков для суммы (RSQ)

Будем хранить массивы $sum$ и $val$ с той же адресацией, что и массив $b$ (см. выше). Операция изменения $\mathop{\rm modify}$ будет состоять в увеличении значения всех ячеек от $l$ до $r-1$ на число $X$. $X$ может быть как положительным, так и отрицательным.

$\mathop{\rm modify}$ имеет аргументы $v, L, R, l, r, X$. Здесь $v$ — номер ячейки в массивах $sum$ и $val$, в которой хранится информация об отрезке $[L;R)$, а $[l;r)\subset[L;R)$ — отрезок, на котором производится изменение.

В первую очередь при рекурсивном вызове $\mathop{\rm modify}$ увеличиваем $sum[v]$ на $X*(r-l)$.

Далее, если $L=l$ и $R=r$, то увеличиваем $val[v]$ на $X$.

Если $r\le(L+R)/2$, то вызываем рекурсивно $\mathop{\rm modify}(2v,L,(L+R)/2,l,r,X)$.

Если $l\ge(L+R)/2$, то вызываем $\mathop{\rm modify}(2v+1,(L+R)/2,R,l,r,X)$.

Иначе разбиваем отрезок $[l,r)$ на два: $[l,(L+R)/2)$ и $[(L+R)/2,r)$. Производим 2 рекурсивных вызова $\mathop{\rm modify}(2v,L,(L+R)/2,l,(L+R)/2,X)$ и $\mathop{\rm modify}(2v+1,(L+R)/2,R,(L+R)/2,r,X)$.

Процедура $\mathop{\rm count}$ вычисления суммы на отрезке модифицируется аналогично.

Если $L=l$ и $R=r$, то значение суммы равно $sum[v]$.

Если $r\le(L+R)/2$, то значение равно $\mathop{\rm count}(2v,L,(L+R)/2,l,r)+val[v]*(r-l)$.

Если $l\ge(L+R)/2$, то значение равно $\mathop{\rm count}(2v+1,(L+R)/2,R,l,r)+val[v]*(r-l)$.

Иначе возвращаем $\mathop{\rm count}(2v,L,(L+R)/2,l,(L+R)/2)+\mathop{\rm count}(2v+1,(L+R)/2,R,(L+R)/2,r)+val[v]*(r-l)$.

Общая сложность операций modify и count составляет $O(\log(n))$.

Дерево отрезков для максимума (RMQ)

Аналогично предыдущему случаю будем хранить массивы $max$ и $val$. Операция $\mathop{\rm modify}$ будет иметь тот же смысл и те же аргументы.

Если $L=l$ и $R=r$, то увеличиваем значения $max[v]$ и $val[v]$ на $X$.

Если $r\le(L+R)/2$, то вызываем рекурсивно $\mathop{\rm modify}(2v,L,(L+R)/2,l,r,X)$.

Если $l\ge(L+R)/2$, то вызываем $\mathop{\rm modify}(2v+1,(L+R)/2,R,l,r,X)$.

Иначе разбиваем отрезок $[l,r)$ на два: $[l,(L+R)/2)$ и $[(L+R)/2,r)$. Производим 2 рекурсивных вызова $\mathop{\rm modify}(2v,L,(L+R)/2,l,(L+R)/2,X)$ и $\mathop{\rm modify}(2v+1,(L+R)/2,R,(L+R)/2,r,X)$.

После рекурсивных вызовов (одного или двух), если они имели место, полагаем $max[v]=\max(max[2v],max[2v+1])+val[v]$.

Осталось привести процедуру count вычисления максимума на отрезке.

Если $L=l$ и $R=r$, то значение максимума равно $max[v]$.

Если $r\le(L+R)/2$, то значение равно $\mathop{\rm count}(2v,L,(L+R)/2,l,r)+val[v]$.

Если $l\ge(L+R)/2$, то значение равно $\mathop{\rm count}(2v+1,(L+R)/2,R,l,r)+val[v]$.

Иначе значение максимума равно $\max(\mathop{\rm count}(2v,L,(L+R)/2,l,(L+R)/2), \mathop{\rm count}(2v+1,(L+R)/2,R,(L+R)/2,r))+val[v]$.

Общая сложность операций modify и count, как и в случае суммы, составляет $O(\log(n))$.

Дополнение

Иногда считается, что RMQ — это не дерево отрезков, а динамическое программирование (называется Sparse table) для нахождения максимума/минимума на отрезке за O(1) с препроцессингом за время O(n log n).

Препроцессинг:

Обозначим $\mathop{\rm f}[i, k]$ — максимум/минимум на отрезке от $i$ до $i+2^k-1$. Массив $\mathop{\rm f}[i, k]$ можно заполнить динамически следующим образом:

1) $\mathop{\rm f}[i, 0] = a[i]$;

2) $\mathop{\rm f}[i, k] = \max(\mathop{\rm f}[i, k-1], \mathop{\rm f}[i+2^{k-1}, k-1])$ или $\mathop{\rm f}[i,k] = \min(\mathop{\rm f}[i, k-1], \mathop{\rm f}[i+2^{k-1}, k-1])$ соответственно.

Вычисление:

Ответ на отрезке $[l,r]$ равен $\max(\mathop{\rm f}[l,lg],\mathop{\rm f}[r-2^{lg}+1,lg])$ (соответственно $\min(\mathop{\rm f}[l,lg],\mathop{\rm f}[r-2^{lg}+1,lg])$), где lg — максимальная степень двойки, не превосходящая $r-l+1$.

Пример:

Рассматриваем диапазон от 1 до 5. Максимальная степень двойки, которая помещается на него, это два, но она не покрывает весь диапазон, а только часть от 1 до 4. Максимум на этом отрезке можно получить, сравнив значения f[1,2] и f[2,2] (максимумы на отрезках от 1 до 4 и от 2 до 5).

Ссылки

• Дерево отрезков, его реализация на C++ и задачи, им решаемые, на сайте e-maxx.ru
• Реализация Дерева отрезков на Java

См. также

• Дерево Фенвика