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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Дерево отрезковструктура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов 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[править | править вики-текст]

Также задачу 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).

Решение за O(1) с препроцессингом и памятью O(N)[править | править вики-текст]

Для такого решения достаточно свести задачу RMQ к задаче LCA, построив декартово дерево из элементов вида (i,a[i]), то есть i - ключ, a[i] - приоритет. Приоритеты должны быть упорядочены снизу вверх, то есть в корне должен стоять элемент с наименьшим a[i]. Очевидно, такое дерево легко построить за O(N), так как все ключи у нас упорядочены (это идущие друг за другом индексы элементов массива).

После этого ответом на любой запрос будет LCA двух вершин (l,a[l]) и (r,a[r]). Индекс LCA будет лежать в [l;r], так как декартово дерево по ключу - двоичное дерево. Благодаря тому, что декартово дерево - пирамида по приоритету, эта же вершина будет иметь наименьший приоритет (значение элемента) из всех, находящихся в [l;r]

Для задачи LCA известны несколько возможных решений за O(1) с препроцессингом и памятью O(N). Такое решение является асимптотически оптимальным.

Ссылки[править | править вики-текст]

См. также[править | править вики-текст]