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

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

Дерево отрезков — структура данных позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов $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]$ при $u < 2 k$ будет храниться число $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]$ используется следующая рекурсиваная процедура count от аргументов $v, L, R, l, r$ . Здесь $v$ — элемент массива $b$ в котором находится значение функции для отрезка $[L; R)$ , а $[l;r)\in[L;R)$ — отрезок, на котором мы хотим посчитать функцию. Если $L = l$ и $R = r$ , то ответ равен $b [v]$ . Если $r\le(L+R)/2$ , то ответ равен $c o u n t (2 v, L,(L + R) / 2, l, r)$ . Если $l\le(L+R)/2$ , то ответ равен $c o u n t (2 v + 1,(L + R) / 2, R, l, r)$ . Иначе отрезок $[l, r)$ можно разбить на два отрезка: $[l,(L + R) / 2)$ и $[(L + R) / 2, r)$ . Тогда ответом будет $f (c o u n t (2 v, L,(L + R) / 2, l,(L + R) / 2), c o u n t (2 v + 1,(L + R) / 2, R,(L + R) / 2, r))$ . Таким образом, вычисление функции на отрезке $[l, r)$ сводится к вычислению функции от $O (log(n))$ элементов массива $b$ , которые соотвествуют некоторым отрезкам $[2 l u;2 l (u + 1))$ .