Изменения

[[Дерево отрезков. Построение|Дерево отрезков]] можно обобщить в естественным образом обобщается на двумерный и, вообще говоря, многомерный случай для решения таких задач. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике. Например, как поиск суммы на прямоугольнике (или гиперпрямоугольной области)она позволяет решать следующую задачу.{{Задача|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|600px|right|Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)]]<tex>n</tex>-мерное дерево отрезков {{---}} обычное дерево отрезков, элементами которого являются деревья отрезков размерности на единицу меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3...\ldots x_p</tex>. ТНеобходимо найти значение некоторой ассоциативной функции на гиперпрямоугольнике.к. при построении одномерного дерева Функция, индексы массива разбиваются на отрезкивычисляющая ответ, тогда при построении многомерного дерева координаты будут обрабатываться сначала по должна работать следующим образом. На вход она принимает <tex>x_1 i</tex>-мерное дерево отрезков, затем по которое соответствует рассматриваемой области (где <tex>x_2i</tex> и так далее... Далее дерево строится рекурсивно: далее координаты по {{---}} количество координатных осей, которые не были рассмотрены), а также <tex>x_1i</tex> обрабатываем по координатам -мерную область, для которой следует вычислить функцию. Вначале она находит <tex>x_2i-1</tex>-мерные деревья отрезков, которые соответствуют отрезку по <tex>x_3p-i+1</tex> координате, и рекурсивно запускается от них (по всем возможным координатамесли текущее дерево одномерное, то функция просто возвращает ответ из соответствующего листа) и далее по аналогии... То есть получаетсяПосле этого считает итоговый результат, что основная идея построения многомерного дерева отрезков - вкладывание деревьев отрезка друг в другаиспользуя полученные после рекурсивных вызовов значения.

Пример задачиДля того, чтобы определить, от каких именно деревьев отрезков следует запускаться рекурсивно, действовать необходимо так же, как и в которой удобно использовать многомерное дерево отрезков==Пример двумерного дерева==Рассмотрим процесс построения предельного случая при <tex>p = 2</tex>одномерном случае.Пусть задан массив элементов размера <tex>n \times m</tex>Т. Упорядочим массив по первой координате и построим на нем дерево отрезкове. После этого для каждого узла дерева строим еще одно дерево отрезков по если текущий отрезок не пересекается с необходимым, то возвращаем нейтральный элемент, если он полностью лежит в необходимом отрезке, то рекурсивно переходим к следующей координате <tex>y</tex>, которые находятся на том же отрезкеиначе разобьем текущий отрезок пополам, и рассмотри отдельно каждую из частей.

К примеру,двумерное дерево размером На рисунке справа показан пример обработки очередной координаты (поиск соответствующих отрезку элементов {{---}} деревьев на <tex>4 \times 4 :1</tex>меньшей мерности).

[[Файл:Многомерное доТаким образом, алгоритм совершит <tex>p</tex> вхождений в рекурсию, каждая итерация которой работает за <tex>O(\log n)</tex> и получим необходимую асимптотику.jpg]]

[[Файл:МдоSegmentTree2DExample.JPGpng|thumb|350px|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> {{---}} общее количество элементов.

==Анализ и оценка структурыЗапрос==Строится такое дерево за линейное времяРассмотрим отличия реализации многомерного и одномерного случаев. На самом деле, отличаются реализации только в двух местах.Структура использует <tex>O(n^p)</tex> памятиВо-первых, если рассматриваемый отрезок совпадает с необходимым, то в одномерном случае функция просто возвращает число, которое находится в текущем элементе массива. В многомерном случае, если рассматриваемая координата не последняя, следует вместо этого узнать значение, рекурсивно перейдя к следующей координате, и отвечает на запрос за <tex>O(log^{p} n)</tex>, где <tex>p</tex>-размерность деревавернуть его.

Ответ на запрос Еще один момент, в которых отличается реализация {{---}} передаваемые в таком дереве будет производиться так же,как и построение: сначала по координате функцию параметры. В многомерном случае кроме всего прочего следует также передать рассматриваемое <tex>x_1p-i+1</tex>-мерное дерево (или кортеж из чисел, затемуказывающих на соответствующие элементы массива), когда дошли до какой-либо вершины по первой координатеа также область, вызвать запрос от этого же дерева по которую следует рассматривать (или <tex>x_2p-i+1</tex> и так далее. Получаетсяпар чисел, что для <tex>n-</tex>мерного дерева запрос выполняется за <tex>O(log (s_{x_1})\cdot log (s_{x_2}обозначающих отрезки на соответствующих координатных осях).Все остальные детали реализации остаются такими же как и в одномерном дереве отрезков..log (s_{x_n}))</tex> (для рассмотренного двумерного дерева будет <tex>log (n) \cdot log (m) </tex> )

В каждом нижеприведенном псевдокоде будут встречены обозначения:* индекс <tex>\mathtt{P}</tex> {{---}} размерность массива из условия задачи,* <tex>\mathtt{\odot}</tex> {{---}} та операция, которую мы считаем на данном многомерном дереве отрезков. В нижеприведенном псевдокоде будет встречен <tex>\varepsilon</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]*e '''else''' '''return''' query(area[], x1, x2, ..., xP, node, 0, m -maxx1, area[P + 2].ru: left, area[http: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</e-maxxtex> query(area[], x1, x2, ...ru, xP, med + 1, rightBorder, max(queryLeft, med + 1), queryRight, node * 2 + 2)</algocode> ==Обновление==Как и в одномерном случае, обновить в массиве необходимо не один элемент, а все, которые отвечают за области, в которых он присутствует. Таким образом, при обработке отрезка по некоторой координате (если она не последняя) следует выполнить следующие действия:* Если рассматриваемый отрезок содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент* Перейдем к следующей координатеЗаметим, что "переходов к следующей координаты" при рассмотрении некоторой координатной оси будет совершено <tex>\log n</segment_tree Дерево отрезков] tex>, а итоговая сложность составит <tex>O(\log^{p} n)<br/tex>. Отдельно следует рассмотреть, что происходит, когда текущее дерево является одномерным (мы рассмотрели все координаты, кроме текущей):* Если рассматриваемый отрезок содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент*FНайдем первую координату, в которой рассматривается больше одного элемента. Обновим значение элемента массива с помощью уже вычисленных значений для разбитого надвое отрезка по этой координате.* Если мы рассматриваем область, состоящую из одного элемента, обновим значение массива. Псевдокод:<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, ... Preparata, MxP, 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]. Shamos ..[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 - Вычислительная геометрия [http1, 0)</code> ==Построение==Построение многомерного дерева отрезков практически ничем не отличается от его обновления. Единственное различие {{---}} если рассматриваемый отрезок состоит из более чем одного элемента, то необходимо рекурсивно вызываться из обеих частей. Псевдокод:<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</pogorskiytex> t[x1][x2].narod.ru.[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>O(n)</tex> времени, где <tex>n</rectqtex> {{---}} общее число элементов в массиве.htm Главы о региональном поиске]

*[[Дерево отрезков. Построение]] <br/>*[[Сжатое многомерное дерево отрезков]] <br/>*[[Многомерное дерево Фенвика]] <br ==Источники информации==* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]* [http://habrahabr.ru/post/131072/)/>Habrahabr {{---}} Двумерное дерево отрезков]  [[Категория: Дискретная математика и алгоритмы]][[Категория: Дерево отрезков]][[Категория: Модификации структур данных]]