Изменения

[[Дерево отрезков. Построение|Дерево отрезков]] естественным образом обобщается на двумерный и , вообще говоря , многомерный случай. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике. Например, она позволяет решать следующую задачу. {{Задача|definition = Дан <tex>p</tex>-мерный массив, где индекс каждого измерения массива может принимать значения от <tex>1 </tex> до <tex>n</tex>. Необходимо уметь изменять значение элемента массива, а также находить сумму на <tex>p</tex>-мерной области. }} Каждую из этих операций многомерное дерево отрезков выполняет за <tex>O(\log^{p} n)</tex>. К примерам задач, решаемых с помощью многомерного дерева отрезков, также можно отнести задачи, которые решаются с помощью одномерного [[Дерево отрезков. Построение|дерева отрезков]], только теперь в многомерном случае, а еще ,например, задачу поиска числа точек в заданном прямоугольнике, которую иначе можно решать при помощи [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)|range tree]], и другие.

[[Файл:SegmentTreeWorking.png|thumb|450px600px|right|Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)]]<tex>n</tex>-мерное дерево отрезков {{---}} обычное дерево отрезков, элементами которого являются деревья отрезков размерности на 1 единицу меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3...\ldots x_p</tex>. Необходимо найти значение некоторой ассоциативной функции на гиперпрямоугольнике.

Для того, чтобы определить, от каких именно деревьев отрезков следует запускаться рекурсивно, действовать необходимо так же, как и в одномерном случае. Т. е. если текущий отрезок не пересекается с необходимым, то возвращаем нейтральный элемент, если он полностью лежит в необходимом отрезке, то рекурсивно переходим к следующей размерностикоординате, иначе разобьем текущий отрезок пополам, и рассмотри отдельно каждую из частей.

На рисунке справа показан пример обработки очередной координаты (поиск соответствующих отрезку элементов {{---}} деревьев на <tex>1 </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>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.

==Многомерный случайЗапрос==Рассмотримотличия реализации многомерного и одномерного случаев. На самом деле, как изменяться функции при переходе отличаются реализации только в двух местах. Во-первых, если рассматриваемый отрезок совпадает с необходимым, то в одномерном случае функция просто возвращает число, которое находится в текущем элементе массива. В многомерном случае, если рассматриваемая координата не последняя, следует вместо этого узнать значение, рекурсивно перейдя к <tex>n</tex>-мерному случаюследующей координате, и вернуть его.

НапримерЕще один момент, для операции обновления дерева отрезков изменения будут следующими. В коде будут присутствовать <tex>n</tex> функций update (для каждой из координат). Реально будут только две различные реализации этих функций (первая, при нахождении необходимых листьев дерева, рекурсивно переходит к следующей координате, вторая в которых отличается реализация {{---}} только возвращает значение из массива)передаваемые в функцию параметры. Мы можем не писать В многомерном случае кроме всего прочего следует также передать рассматриваемое <tex>np-i+1</tex> одинаковых реализаций в коде-мерное дерево (или кортеж из чисел, указывающих на соответствующие элементы массива), а также область, но тогда дерево отрезков придется хранить не в которую следует рассматривать (или <tex>np-i+1</tex>-мерном массивепар чисел, а обозначающих отрезки на соответствующих координатных осях). Все остальные детали реализации остаются такими же как и в одномерном (это не сильно усложнит реализацию, но понятность кода уменьшится)дереве отрезков.

Рассмотрим более подробно устройство такой функции. В качестве параметров она должна принимать областькаждом нижеприведенном псевдокоде будут встречены обозначения:* индекс <tex>\mathtt{P}</tex> {{---}} размерность массива из условия задачи, на которой считается * <tex>\mathtt{\odot}</tex> {{---}} та операция, информацию о том, из каких ячеек массива которую мы рекурсивно спустились, отрезок, который обрабатывается по текущей координате и необходимый нам отрезок, а также номер текущей ячейки массивасчитаем на данном многомерном дереве отрезков.

В нижеприведенном псевдокоде будет встречен <tex>\varepsilon</tex> operationCalc(area[], x1, x2, {{---}} нейтральный элемент..., xP, leftBorder, rightBorder, needLeft, needRight, vertex)

Псевдокод:<code> '''void''' query('''int''' area[], '''int''' x1, '''int''' x2, ..., '''int''' xP, '''int''' leftBorder, '''int''' rightBorder, '''int''' queryLeft, '''int''' queryRight, '''int''' node) '''if needLeft ''' queryLeft > queryRight '''return''' <tex> needRight\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>

Потом==Обновление==Как и в одномерном случае, обновить в массиве необходимо не один элемент, а все, которые отвечают за области, в которых он присутствует. Таким образом, при обработке отрезка по некоторой координате (если текущий она не последняя) следует выполнить следующие действия:* Если рассматриваемый отрезок совпадает с искомымсодержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, необходимо перейти где находится необходимый элемент* Перейдем к поиску по следующей координатеЗаметим, что "переходов к следующей координаты" при рассмотрении некоторой координатной оси будет совершено <tex>\log n</tex>, а итоговая сложность составит <tex>O(\log^{p} n)</tex>.

if leftBorder == needLeft && rightBorder == needRightОтдельно следует рассмотреть, что происходит, когда текущее дерево является одномерным (мы рассмотрели все координаты, кроме текущей): return operationCalc(area[]* Если рассматриваемый отрезок содержит больше одного элемента, x1разобьем его на две части и рекурсивно перейдем в ту, x2где находится необходимый элемент* Найдем первую координату, в которой рассматривается больше одного элемента.Обновим значение элемента массива с помощью уже вычисленных значений для разбитого надвое отрезка по этой координате.., xP, vertex, 0, m - 1* Если мы рассматриваем область, area[P + 2].leftсостоящую из одного элемента, area[P + 2]обновим значение массива.right, 0)

Если же отрезок не совпадаетПсевдокод:<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> 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>

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)

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]