Изменения

[[Дерево отрезков. Построение|Дерево отрезков]] естественным образом обобщается на двумерный и, вообще говоря, многомерный случай. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике. Например, она позволяет решать следующую задачу. {{Задача|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]], и другие.

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

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

Пусть необходимо хранить дерево отрезков для <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>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.

<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''' neutral<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>\timesodot</tex> query(area[], x1, x2, ..., xP, med + 1, rightBorder, max(queryLeft, med + 1), queryRight, node * 2 + 2)</code>

<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

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>\timesodot</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>

Построение многомерного дерева отрезков практически ничем не отличается от его обновления. Единственное различие {{---}} если рассматриваемый отрезок состоит из более чем одного элемента, то необходимо рекурсивно вызываться из обоих обеих частей.

<code> '''void''' build('''int''' x1, '''int''' x2, ..., '''int''' xP, '''int''' x1Left, '''int''' x1Right, '''int''' x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, rightBorder, node) '''ifint''' 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) '''ifint''' последняя координата xPLeft, '''forint''' I = 1..n xPRight, '''ifint''' xILeft != xIRigth t[x1][x2]...[xP][node] = t[x1][x2]...[xI * 2 + 1]...[node] <tex>\times</tex> t[x1][x2]...[xI * 2 + 2]...[node]leftBorder, '''returnint''' t[x1][x2]...[xP][node] = data[x1Left][x2Left]...[xPLeft][node] rightBorder, '''elseint'''node)

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>