47
правок
Изменения
м
''' if''' queryLeft > queryRight ''' return''' neutral ''' if''' leftBorder == queryLeft && rightBorder == queryRight ''' if''' последняя координата ''' return''' t[x1][x2]...[xP][node] ''' else''' ''' return''' query(area[], x1, x2, ..., xP, node, 0, m - 1, area[P + 2].left, area[P + 2].right, 0) med = (leftBorder + rightBorder) / 2 ''' return''' query(area[], x1, x2, ..., xP, leftBorder, med, queryLeft, min(queryRight, med), node * 2 + 1) <tex>\times</tex> query(area[], x1, x2, ..., xP, med + 1, rightBorder, max(queryLeft, med + 1), queryRight, node * 2 + 2)</code>
''' if''' leftBorder != rightBorder med = (leftBorder + rightBorder) / 2 '''if''' med >= newElem.x(P+1) update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, med, node * 2 + 1) '''else''' update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, med + 1, rightBorder, node * 2 + 2) ''' if''' последняя координата ''' for''' I = 1..n ''' if''' xILeft != xIRigth t[x1][x2]...[xP][node] = t[x1][x2]...[xI * 2 + 1]...[node] <tex>\times</tex> t[x1][x2]...[xI * 2 + 2]...[node] ''' return''' t[x1][x2]...[xP][node] = newElem.value ''' else''' ''' if''' leftBorder != rightBorder update(newElem, x1, x2, ..., xP, node, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)</code>
''' if''' leftBorder != rightBorder med = (leftBorder + rightBorder) / 2 update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, med, node * 2 + 1) update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, med + 1, rightBorder, node * 2 + 2) ''' if''' последняя координата ''' for''' I = 1..n ''' if''' xILeft != xIRigth t[x1][x2]...[xP][node] = t[x1][x2]...[xI * 2 + 1]...[node] <tex>\times</tex> t[x1][x2]...[xI * 2 + 2]...[node] ''' return''' t[x1][x2]...[xP][node] = data[x1Left][x2Left]...[xPLeft][node] ''' else''' ''' if''' leftBorder != rightBorder update(newElem, x1, x2, ..., xP, node, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)</code>
Псевдокод отформатирован, константы взяты в tex
[[Дерево отрезков. Построение|Дерево отрезков]] естественным образом обобщается на двумерный и, вообще говоря, многомерный случай. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике. Например, она позволяет решать следующую задачу. Дан <tex>p</tex>-мерный массив, где индекс каждого измерения массива может принимать значения от <tex>1 </tex> до <tex>n</tex>. Необходимо уметь изменять значение элемента массива, а также находить сумму на <tex>p</tex>-мерной области. Каждую из этих операций многомерное дерево отрезков выполняет за <tex>O(\log^{p} n)</tex>.
==Принцип работы==
[[Файл:SegmentTreeWorking.png|thumb|600px|right|Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)]]
<tex>n</tex>-мерное дерево отрезков {{---}} обычное дерево отрезков, элементами которого являются деревья отрезков размерности на 1 единицу меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3...x_p</tex>. Необходимо найти значение некоторой ассоциативной функции на гиперпрямоугольнике.
Функция, вычисляющая ответ, должна работать следующим образом. На вход она принимает <tex>i</tex>-мерное дерево отрезков, которое соответствует рассматриваемой области (где <tex>i</tex> {{---}} количество координатных осей, которые не были рассмотрены), а также <tex>i</tex>-мерную область, для которой следует вычислить функцию. Вначале она находит <tex>i-1</tex>-мерные деревья отрезков, которые соответствуют отрезку по <tex>p-i+1</tex> координате, и рекурсивно запускается от них (если текущее дерево одномерное, то функция просто возвращает ответ из соответствующего листа). После этого считает итоговый результат, используя полученные после рекурсивных вызовов значения.
Для того, чтобы определить, от каких именно деревьев отрезков следует запускаться рекурсивно, действовать необходимо так же, как и в одномерном случае. Т. е. если текущий отрезок не пересекается с необходимым, то возвращаем нейтральный элемент, если он полностью лежит в необходимом отрезке, то рекурсивно переходим к следующей координате, иначе разобьем текущий отрезок пополам, и рассмотри отдельно каждую из частей.
На рисунке справа показан пример обработки очередной координаты (поиск соответствующих отрезку элементов {{---}} деревьев на <tex>1 </tex> меньшей мерности).
Таким образом, алгоритм совершит <tex>p</tex> вхождений в рекурсию, каждая итерация которой работает за <tex>O(\log n)</tex> и получим необходимую асимптотику.
Псевдокод:
<code>
query(area[], x1, x2, ..., xP, leftBorder, rightBorder, queryLeft, queryRight, node)
==Обновление==
Псевдокод:
<code>
update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, rightBorder, node)
==Построение==
Псевдокод:
<code>
build(x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, rightBorder, node)
Заметим, что построение дерева требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} общее число элементов в массиве.
