[[Дерево отрезков. Построение|Дерево отрезков]] естественным образом обобщается на двумерный и , вообще говоря , многомерный случай. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике за . Например, она позволяет решать следующую задачу.{{Задача|definition = Дан <tex>O(\log^{p} </tex>-мерный массив, где индекс каждого измерения массива может принимать значения от <tex>1</tex> до <tex>n)</tex>. Необходимо уметь изменять значение элемента массива, где а также находить сумму на <tex>p</tex> {{---мерной области. }} размерность пространства, а Каждую из этих операций многомерное дерево отрезков выполняет за <tex>O(\log^{p} n)</tex> {{---}} ширина гиперкуба на котором производятся вычисления.
==Структура==<tex>n</tex>-мерное дерево отрезков {{---}} обычное дерево отрезковК примерам задач, элементами которого являются деревья решаемых с помощью многомерного дерева отрезков размерности на 1 меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2также можно отнести задачи, x_3которые решаются с помощью одномерного [[Дерево отрезков...x_p</tex>. Необходимо вычислять некоторую ассоциативную функцию на гиперпрямоугольнике. Для этого сначала найдем элементы Построение|дереваотрезков]], соответствующие <tex>x_1</tex> координате. Для каждого из этих элементов рекурсивно перейдем в соответствующие им деревья отрезков и только теперь в них найдем элементымногомерном случае, отвечающие соответствующим координатам <tex>x_2</tex> исходной гиперпрямоугольной областиа еще , и т. д. Таким образомнапример, алгоритм совершит <tex>p</tex> вхождений задачу поиска числа точек в рекурсиюзаданном прямоугольнике, каждая итерация которой работает которую иначе можно решать при помощи [[Перечисление точек в произвольном прямоугольнике за <tex>On * log ^(\log d - 1) n(range tree)</tex> |range tree]], и получим необходимую асимптотикудругие.
==Двумерное дерево отрезковПринцип работы==Рассмотрим следующую задачу[[Файл:SegmentTreeWorking.png|thumb|600px|right|Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)]]<tex>n</tex>-мерное дерево отрезков {{Задача|definition=Дано поле размером ---}} обычное дерево отрезков, элементами которого являются деревья отрезков размерности на единицу меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>N x_1, x_2, x_3 \times Mldots x_p</tex>, заполненное некоторыми числами. Необходимо уметь обрабатывать два типа запросов: * Изменить некоторый элемент* Посчитать найти значение некоторой ассоциативной функции на гиперпрямоугольнике. Функция, вычисляющая ответ, должна работать следующим образом. На вход она принимает <tex>\timesi</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> и получим необходимую асимптотику.
==Хранение==
[[Файл:SegmentTree2DExample.png|thumb|250px350px|right|Пример двумерного дерева отрезков для 16 элементов]]Двумерное Пусть необходимо хранить дерево отрезков для <tex>p</tex>-мерной области, размеры которой <tex>n_1 \times n_2 \times \ldots \times n_p</tex>. Удобнее всего это делать с помощью <tex>p</tex>-мерного массива. Однако его размеры по каждой координате, так же как и в одномерном случае, должны превышать размеры соответствующего отрезка в 4 раза. На самом деле нам нужно хранить <tex>2n</tex> чисел, но, если мы хотим, чтобы правый и левый сын некоторой вершины <tex>i</tex> находились на <tex> 2i + 1</tex> и <tex>2i + 2</tex> месте, то, если длина отрезка не является степенью двойки, некоторые элементы массива могут быть не задействованы, поэтому, в худшем случае, может понадобиться массив, размер которого в 4 раза превышает количество элементов. Т. е. потребуется массив размером <tex>4 n_1 \times 4 n_2 \times \ldots \times 4 n_p</tex>. Так двумерное дерево отрезков удобно хранить в виде массива, размером <tex>4N \times 4M</tex>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.
На рисунке справа показан пример дерева отрезков для суммы на массиве 4 на 4, заполненного числами от 1 от 16. Например, в элементе <tex>a[2][0] = 100</tex> хранится сумма элементов, соответствующих отрезку <tex>[2..3]</tex> по первой координате и <tex>[0..3]</tex> по второй в исходном массиве. А в ячейке <tex>a[0][0] = 136</tex> хранится сумма всех элементов.
Заметим, что в общем случае для хранения <tex>p</tex>-мерного дерева отрезков требуется <tex>4^p n</tex> памяти, где <tex>n</tex> {{---}} общее количество элементов.
==Псевдокод для двумерного случаяЗапрос==Построение: // first call - buildX(0, 0, n, aРассмотрим отличия реализации многомерного и одномерного случаев. На самом деле, t) // a отличаются реализации только в двух местах. Во- исходный массив // t - массив дерева отрезков // [leftXпервых, rightX) - полуинтервал buildX(vertexXесли рассматриваемый отрезок совпадает с необходимым, leftXто в одномерном случае функция просто возвращает число, rightXкоторое находится в текущем элементе массива. В многомерном случае, a[][]если рассматриваемая координата не последняя, t[][]) if leftX != rightX mx = (leftX + rightX + 1) / 2 buildX(vertexX * 2 + 1, leftXследует вместо этого узнать значение, mxрекурсивно перейдя к следующей координате, a, t) buildX(vertexX * 2 + 2, mx, rightX, a, t) buildY(vertexX, leftX, rightX, 0, 0, m, a, t) buildY(vertexX, leftX, rightX, vertexY, leftY, rightY, a[][], t[][]) if leftY == rightY if leftX == rightX t[vertexX][vertexY] = a[leftX][leftY] else t[vertexX][vertexY] = t[vertexX * 2 + 1][vertexY] <tex>\times</tex> t[vertexX * 2 + 2][vertexY] else my = (leftY + rightY + 1) / 2 buildY(vertexX, leftX, rightX, vertexY * 2 + 1, leftY, my, a, t) buildY(vertexX, leftX, rightX, vertexY * 2 + 2, my, rightY, a, t) t[vertexX][vertexY] = t[vertexX][vertexY * 2 + 1] <tex>\times</tex> t[vertexX][vertexY * 2 + 2]и вернуть его.
Подсчет некоторой функции от элементовЕще один момент, лежащих в прямоугольной области: // first call которых отличается реализация {{-- sumX(0, 0, n - 1, leftX, rightX, leftY, rightY, t) sumX(vertexX, leftBorderX, rightBorderX, leftX, rightX, leftY, rightY, t[][]) if leftX }} передаваемые в функцию параметры. В многомерном случае кроме всего прочего следует также передать рассматриваемое <tex> rightX return 0 if leftX == leftBorderX && rightX == rightBorderX return sumY(vertexX, 0, 0, m p- 1, leftY, rightY) tmx = (leftBorderX + rightBorderX) / 2 return sumX(vertexX * 2 i+ 1, leftBorderX, tmx, leftX, min(rightX, tmx), leftY, rightY, t) <tex>\times</tex> sumX-мерное дерево (vertexX * 2 + 2или кортеж из чисел, tmx + 1, rightBorderX, max(leftX, tmx + 1указывающих на соответствующие элементы массива), rightX, leftY, rightYа также область, t) sumYкоторую следует рассматривать (vertexX, vertexY, leftBorderY, rightBorderY, leftY, rightY) if leftY или <tex> rightY return 0 if leftY == leftBorderY && rightY == rightBorderY return t[vertexX][vertexY] tmy = (leftBorderY + rightBorderY) / 2 return sumY(vertexX, vertexY * 2 p-i+ 1, leftBorderY, tmy, leftY, min(rightY, tmy), t) <tex>\times</tex> sumY(vertexX, vertexY * 2 + 2, tmy + 1пар чисел, rightBorderY, max(leftY, tmy + 1), rightY, tобозначающих отрезки на соответствующих координатных осях). Все остальные детали реализации остаются такими же как и в одномерном дереве отрезков.
Обновление элементаВ каждом нижеприведенном псевдокоде будут встречены обозначения: // first call - updateX(0, 0, n - 1, x, y, val, t) updateX(vertexX, leftX, rightX, x, y, val, t[][]) if leftX != rightX mx = (leftX + rightX) / 2 if x <= mx updateX(vertexX * 2 + 1, leftX, mx, x, y, val, t) else updateX(vertexX * 2 + 2, mx + 1, rightX, x, y, val, t) updateY(vertexX, leftX, rightX, 0, 0, m - 1, x, y, val, t) updateY(vertexX, leftX, rightX, vertexY, leftY, rightY, x, y, val, t[][]) if leftY == rightY if leftX == rightX t[vertexX][vertexY] = val else t[vertexX][vertexY] = t[vertexX * 2 + 1][vertexY] индекс <tex>\timesmathtt{P}</tex> t[vertexX * 2 + 2][vertexY] else my = (leftY + rightY) / 2 if y <= my updateY(vertexX, leftX, rightX, vertexY * 2 + 1, leftY, my, x, y, val, t) else updateY(vertexX, leftX, rightX, vertexY * 2 + 2, my + 1{{---}} размерность массива из условия задачи, rightY, x, y, val, t) t[vertexX][vertexY] = t[vertexX][vertexY * 2 + 1] <tex>\timesmathtt{\odot}</tex> t[vertexX][vertexY * 2 + 2] {{---}} та операция, которую мы считаем на данном многомерном дереве отрезков.
==Многомерный случай==Рассмотрим, как изменяться функции при переходе к В нижеприведенном псевдокоде будет встречен <tex>n\varepsilon</tex> {{-мерному случаю--}} нейтральный элемент.
Например, для операции обновления дерева отрезков изменения будут следующими. В коде будут присутствовать <tex>n</tex> функций update (для каждой из координат). Реально будут только две различные реализации этих функций (первая, при нахождении необходимых листьев дерева, рекурсивно переходит к следующей координате, вторая {{---}} только возвращает значение из массива). Мы можем не писать <tex>n</tex> одинаковых реализаций в коде, но тогда дерево отрезков придется хранить не в <tex>n</tex>-мерном массиве, а в одномерном (это не сильно усложнит реализацию, но понятность кода уменьшится).
Рассмотрим более подробно устройство такой функцииПсевдокод:<code> '''void''' query('''int''' area[], '''int''' x1, '''int''' x2, ..., '''int''' xP, '''int''' leftBorder, '''int''' rightBorder, '''int''' queryLeft, '''int''' queryRight, '''int''' node) '''if''' queryLeft > queryRight '''return''' <tex>\varepsilon</tex> '''if''' leftBorder == queryLeft '''and''' 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>\odot</tex> query(area[], отрезокx1, который обрабатывается по текущей координате и необходимый нам отрезокx2, а также номер текущей ячейки массива..., xP, med + 1, rightBorder, max(queryLeft, med + 1), queryRight, node * 2 + 2)</code>
operationCalc(area[]==Обновление==Как и в одномерном случае, обновить в массиве необходимо не один элемент, x1а все, x2которые отвечают за области, в которых он присутствует...Таким образом, xPпри обработке отрезка по некоторой координате (если она не последняя) следует выполнить следующие действия:* Если рассматриваемый отрезок содержит больше одного элемента, leftBorderразобьем его на две части и рекурсивно перейдем в ту, rightBorderгде находится необходимый элемент* Перейдем к следующей координатеЗаметим, needLeftчто "переходов к следующей координаты" при рассмотрении некоторой координатной оси будет совершено <tex>\log n</tex>, needRight, vertexа итоговая сложность составит <tex>O(\log^{p} n)</tex>.
Вначале Отдельно следует проверитьрассмотреть, что обрабатываемый происходит, когда текущее дерево является одномерным (мы рассмотрели все координаты, кроме текущей):* Если рассматриваемый отрезок не пустой (иначе вернуть нейтральный содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент * Найдем первую координату, в которой рассматривается больше одного элемента. Обновим значение элемента массива с помощью уже вычисленных значений для операции)разбитого надвое отрезка по этой координате.* Если мы рассматриваем область, состоящую из одного элемента, обновим значение массива.
Псевдокод:<code> '''void''' update('''int''' newElem, '''int''' x1, '''int''' x2, ..., '''int''' xP, '''int''' x1Left, '''int''' x1Right, '''int''' x2Left, '''int''' x2Right, ..., '''int''' xPLeft, '''int''' xPRight, '''int''' leftBorder, '''int''' rightBorder, '''int''' node) '''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>\odot</tex> rigthBordert[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 == needLeft && rightBorder == needRight
return operationCalc(area[], x1, x2, ..., xP, vertex, 0, m - 1, area[P + 2].left, area[P + 2].right, 0)
Если же отрезок не совпадает, то делим его пополам и рекурсивно вызываемся от его частей
med = (leftBorder + rightBorder) / 2
return operationCalc(area[], x1, x2, ..., xP, leftBorder, med, needLeft, min(needRight, med), vertex * 2 + 1) <tex>\times</tex>
operationCalc(area[], x1, x2, ..., xP, med + 1, rightBorder, max(needLeft, med + 1), needRight, vertex * 2 + 2)
В реализации для последней координаты вместо рекурсивного перехода следует вернуть значение из массива
if leftBorder == needLeft && rightBorder == needRight
return t[x1][x2]...[xP][vertex]
Теперь рассмотрим операцию обновления. По аналогии напишем <tex>n</tex> функций, в каждой из которых сделаем следующее:
* Если рассматриваемый отрезок содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент
* Перейдем к следующей координате или обновим массив (для последней координаты)
Псевдокод:
<code>
'''void''' build('''int''' x1, '''int''' x2, ..., '''int''' xP, '''int''' x1Left, '''int''' x1Right, '''int''' x2Left, '''int''' x2Right, ..., '''int''' xPLeft, '''int''' xPRight, '''int''' leftBorder,
'''int''' rightBorder, '''int''' node)
'''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 != xIRight
t[x1][x2]...[xP][node] = t[x1][x2]...[xI * 2 + 1]...[node] <tex>\odot</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>
update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ...Заметим, xPLeft, xPRight, leftBorder, rightBorder, vertex) if leftBorder == rightBorder if последняя координата for I = 1..n if xILeft != xIRigth t[x1][x2]...[xP][vertex] = t[x1][x2]...[xI * 2 + 1]...[vertex] что построение дерева требует <tex>\timesO(n)</tex> t[x1][x2]...[xI * 2 + 2]...[vertex] return t[x1][x2]...[xP][vertex] = newElem.value else update(newElemвремени, x1, x2, ..., xP, vertex, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0) else med = (leftBorder + rightBorder) где <tex>n</ 2 if med tex>= newElem.x(P+1) update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, med, vertex * 2 + 1) else update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, med + 1, vertex * 2 + 2) update(newElem, x1, x2, ..., xP, vertex, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0) ==Источники==* [http://e-maxx.ru/algo/segment_tree Дерево отрезков {{---}} e-maxx.ru]* [http://habrahabr.ru/post/131072/)/ Двумерное дерево отрезков {{---}} habrahabrобщее число элементов в массиве.ru]
==См. также==
*[[Сжатое многомерное дерево отрезков]]
*[[Многомерное дерево Фенвика]]
==Источники информации==
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
* [http://habrahabr.ru/post/131072/)/ Habrahabr {{---}} Двумерное дерево отрезков]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
[[Категория: Модификации структур данных]]
