Многомерное дерево отрезков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(многомерный случай)
(Построение)
(не показано 47 промежуточных версий 6 участников)
Строка 1: Строка 1:
[[Дерево отрезков. Построение|Дерево отрезков]] естественным образом обобщается на двумерный и вообще говоря многомерный случай. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике за <tex>O(\log^{p} n)</tex>, где <tex>p</tex> {{---}} размерность пространства, а <tex>n</tex> {{---}} ширина гиперкуба на котором производятся вычисления.
+
[[Дерево отрезков. Построение|Дерево отрезков]] естественным образом обобщается на двумерный и, вообще говоря, многомерный случай. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике. Например, она позволяет решать следующую задачу.{{Задача|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...x_p</tex>. Необходимо вычислять некоторую ассоциативную функцию на гиперпрямоугольнике. Для этого сначала найдем элементы дерева, соответствующие <tex>x_1</tex> координате. Для каждого из этих элементов рекурсивно перейдем в соответствующие им деревья отрезков и в них найдем элементы, отвечающие соответствующим координатам <tex>x_2</tex> исходной гиперпрямоугольной области, и т. д. Таким образом, алгоритм совершит <tex>p</tex> вхождений в рекурсию, каждая итерация которой работает за <tex>O(\log n)</tex> и получим необходимую асимптотику.
 
  
==Двумерное дерево отрезков==
+
==Принцип работы==
Рассмотрим следующую задачу.
+
[[Файл:SegmentTreeWorking.png|thumb|600px|right|Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)]]
{{Задача
+
<tex>n</tex>-мерное дерево отрезков {{---}} обычное дерево отрезков, элементами которого являются деревья отрезков размерности на единицу меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3 \ldots x_p</tex>. Необходимо найти значение некоторой ассоциативной функции на гиперпрямоугольнике.
|definition=
+
 
Дано поле размером <tex>N \times M</tex>, заполненное некоторыми числами. Необходимо уметь обрабатывать два типа запросов:
+
Функция, вычисляющая ответ, должна работать следующим образом. На вход она принимает <tex>i</tex>-мерное дерево отрезков, которое соответствует рассматриваемой области (где <tex>i</tex> {{---}} количество координатных осей, которые не были рассмотрены), а также <tex>i</tex>-мерную область, для которой следует вычислить функцию. Вначале она находит <tex>i-1</tex>-мерные деревья отрезков, которые соответствуют отрезку по <tex>p-i+1</tex> координате, и рекурсивно запускается от них (если текущее дерево одномерное, то функция просто возвращает ответ из соответствующего листа). После этого считает итоговый результат, используя полученные после рекурсивных вызовов значения.
* Изменить некоторый элемент
+
 
* Посчитать значение некоторой ассоциативной функции <tex>\times</tex> на прямоугольной области
+
Для того, чтобы определить, от каких именно деревьев отрезков следует запускаться рекурсивно, действовать необходимо так же, как и в одномерном случае. Т. е. если текущий отрезок не пересекается с необходимым, то возвращаем нейтральный элемент, если он полностью лежит в необходимом отрезке, то рекурсивно переходим к следующей координате, иначе разобьем текущий отрезок пополам, и рассмотри отдельно каждую из частей.
}}
+
 
 +
На рисунке справа показан пример обработки очередной координаты (поиск соответствующих отрезку элементов {{---}} деревьев на <tex>1</tex> меньшей мерности).
 +
 
 +
Таким образом, алгоритм совершит <tex>p</tex> вхождений в рекурсию, каждая итерация которой работает за <tex>O(\log n)</tex> и получим необходимую асимптотику.
  
 
==Хранение==
 
==Хранение==
[[Файл:SegmentTree2DExample.png|thumb|250px|right|Пример двумерного дерева отрезков для 16 элементов]]
+
[[Файл:SegmentTree2DExample.png|thumb|350px|right|Пример двумерного дерева отрезков для 16 элементов]]
Двумерное дерево отрезков удобно хранить в виде массива, размером <tex>4N \times 4M</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>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.
  
 
На рисунке справа показан пример дерева отрезков для суммы на массиве 4 на 4, заполненного числами от 1 от 16. Например, в элементе <tex>a[2][0] = 100</tex> хранится сумма элементов, соответствующих отрезку <tex>[2..3]</tex> по первой координате и <tex>[0..3]</tex> по второй в исходном массиве. А в ячейке <tex>a[0][0] = 136</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> хранится сумма всех элементов.
Строка 23: Строка 26:
 
Заметим, что в общем случае для хранения <tex>p</tex>-мерного дерева отрезков требуется <tex>4^p n</tex> памяти, где <tex>n</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]
 
  
Подсчет некоторой функции от элементов, лежащих в прямоугольной области:
+
Еще один момент, в которых отличается реализация {{---}} передаваемые в функцию параметры. В многомерном случае кроме всего прочего следует также передать рассматриваемое <tex>p-i+1</tex>-мерное дерево (или кортеж из чисел, указывающих на соответствующие элементы массива), а также область, которую следует рассматривать (или <tex>p-i+1</tex> пар чисел, обозначающих отрезки на соответствующих координатных осях). Все остальные детали реализации остаются такими же как и в одномерном дереве отрезков.
// first call - sumX(0, 0, n - 1, leftX, rightX, leftY, rightY, t)
 
 
sumX(vertexX, leftBorderX, rightBorderX, leftX, rightX, leftY, rightY, t[][])
 
  if leftX > rightX
 
  return 0
 
  if leftX == leftBorderX && rightX == rightBorderX
 
  return sumY(vertexX, 0, 0, m - 1, leftY, rightY)
 
  tmx = (leftBorderX + rightBorderX) / 2
 
  return sumX(vertexX * 2 + 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 > rightY
 
  return 0
 
  if leftY == leftBorderY && rightY == rightBorderY
 
  return t[vertexX][vertexY]
 
  tmy = (leftBorderY + rightBorderY) / 2
 
  return sumY(vertexX, vertexY * 2 + 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)
+
* индекс <tex>\mathtt{P}</tex> {{---}} размерность массива из условия задачи,
+
* <tex>\mathtt{\odot}</tex> {{---}} та операция, которую мы считаем на данном многомерном дереве отрезков.
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>\times</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>\times</tex> t[vertexX][vertexY * 2 + 2] 
 
  
==Многомерный случай==
+
В нижеприведенном псевдокоде будет встречен <tex>\varepsilon</tex> {{---}} нейтральный элемент.
Рассмотрим, как изменяться функции при переходе к <tex>n</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, needRight, vertex)
+
==Обновление==
 +
Как и в одномерном случае, обновить в массиве необходимо не один элемент, а все, которые отвечают за области, в которых он присутствует. Таким образом, при обработке отрезка по некоторой координате (если она не последняя) следует выполнить следующие действия:
 +
* Если рассматриваемый отрезок содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент
 +
* Перейдем к следующей координате
 +
Заметим, что "переходов к следующей координаты" при рассмотрении некоторой координатной оси будет совершено <tex>\log n</tex>, а итоговая сложность составит <tex>O(\log^{p} n)</tex>.
  
Вначале следует проверить, что обрабатываемый отрезок не пустой (иначе вернуть нейтральный элемент для операции)
+
Отдельно следует рассмотреть, что происходит, когда текущее дерево является одномерным (мы рассмотрели все координаты, кроме текущей):
 +
* Если рассматриваемый отрезок содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент
 +
* Найдем первую координату, в которой рассматривается больше одного элемента. Обновим значение элемента массива с помощью уже вычисленных значений для разбитого надвое отрезка по этой координате.
 +
* Если мы рассматриваем область, состоящую из одного элемента, обновим значение массива.
  
  if leftBorder > rigthBorder
+
Псевдокод:
  return 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>
  
Потом, если текущий отрезок совпадает с искомым, необходимо перейти к поиску по следующей координате
+
==Построение==
 +
Построение многомерного дерева отрезков практически ничем не отличается от его обновления. Единственное различие {{---}} если рассматриваемый отрезок состоит из более чем одного элемента, то необходимо рекурсивно вызываться из обоих частей.
  
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)
+
Заметим, что построение дерева требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} общее число элементов в массиве.
  if leftBorder == rightBorder
 
  if последняя координата
 
    for I = 1..n
 
    if xILeft != xIRigth
 
      t[x1][x2]...[xP][vertex] = t[x1][x2]...[xI * 2 + 1]...[vertex] <tex>\times</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) / 2
 
  if med >= 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]
 
  
 
==См. также==
 
==См. также==
Строка 157: Строка 113:
 
*[[Сжатое многомерное дерево отрезков]]
 
*[[Сжатое многомерное дерево отрезков]]
 
*[[Многомерное дерево Фенвика]]
 
*[[Многомерное дерево Фенвика]]
 +
 +
==Источники информации==
 +
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
 +
* [http://habrahabr.ru/post/131072/)/ Habrahabr {{---}} Двумерное дерево отрезков]
 +
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дерево отрезков]]
 
[[Категория: Дерево отрезков]]
 +
[[Категория: Модификации структур данных]]

Версия 17:32, 6 июня 2015

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

Задача:
Дан [math]p[/math]-мерный массив, где индекс каждого измерения массива может принимать значения от [math]1[/math] до [math]n[/math]. Необходимо уметь изменять значение элемента массива, а также находить сумму на [math]p[/math]-мерной области.

Каждую из этих операций многомерное дерево отрезков выполняет за [math]O(\log^{p} n)[/math].

К примерам задач, решаемых с помощью многомерного дерева отрезков, также можно отнести задачи, которые решаются с помощью одномерного дерева отрезков, только теперь в многомерном случае, а еще ,например, задачу поиска числа точек в заданном прямоугольнике, которую иначе можно решать при помощи range tree, и другие.

Принцип работы

Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)

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

Функция, вычисляющая ответ, должна работать следующим образом. На вход она принимает [math]i[/math]-мерное дерево отрезков, которое соответствует рассматриваемой области (где [math]i[/math] — количество координатных осей, которые не были рассмотрены), а также [math]i[/math]-мерную область, для которой следует вычислить функцию. Вначале она находит [math]i-1[/math]-мерные деревья отрезков, которые соответствуют отрезку по [math]p-i+1[/math] координате, и рекурсивно запускается от них (если текущее дерево одномерное, то функция просто возвращает ответ из соответствующего листа). После этого считает итоговый результат, используя полученные после рекурсивных вызовов значения.

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

На рисунке справа показан пример обработки очередной координаты (поиск соответствующих отрезку элементов — деревьев на [math]1[/math] меньшей мерности).

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

Хранение

Пример двумерного дерева отрезков для 16 элементов

Пусть необходимо хранить дерево отрезков для [math]p[/math]-мерной области, размеры которой [math]n_1 \times n_2 \times \ldots \times n_p[/math]. Удобнее всего это делать с помощью [math]p[/math]-мерного массива. Однако его размеры по каждой координате, так же как и в одномерном случае, должны превышать размеры соответствующего отрезка в 4 раза. На самом деле нам нужно хранить [math]2n[/math] чисел, но, если мы хотим, чтобы правый и левый сын некоторой вершины [math]i[/math] находились на [math] 2i + 1[/math] и [math]2i + 2[/math] месте, то, если длина отрезка не является степенью двойки, некоторые элементы массива могут быть не задействованы, поэтому, в худшем случае, может понадобиться массив, размер которого в 4 раза превышает количество элементов. Т. е. потребуется массив размером [math]4 n_1 \times 4 n_2 \times \ldots \times 4 n_p[/math]. Так двумерное дерево отрезков удобно хранить в виде массива, размером [math]4N \times 4M[/math]. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.

На рисунке справа показан пример дерева отрезков для суммы на массиве 4 на 4, заполненного числами от 1 от 16. Например, в элементе [math]a[2][0] = 100[/math] хранится сумма элементов, соответствующих отрезку [math][2..3][/math] по первой координате и [math][0..3][/math] по второй в исходном массиве. А в ячейке [math]a[0][0] = 136[/math] хранится сумма всех элементов.

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

Заметим, что в общем случае для хранения [math]p[/math]-мерного дерева отрезков требуется [math]4^p n[/math] памяти, где [math]n[/math] — общее количество элементов.

Запрос

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

Еще один момент, в которых отличается реализация — передаваемые в функцию параметры. В многомерном случае кроме всего прочего следует также передать рассматриваемое [math]p-i+1[/math]-мерное дерево (или кортеж из чисел, указывающих на соответствующие элементы массива), а также область, которую следует рассматривать (или [math]p-i+1[/math] пар чисел, обозначающих отрезки на соответствующих координатных осях). Все остальные детали реализации остаются такими же как и в одномерном дереве отрезков.

В каждом нижеприведенном псевдокоде будут встречены обозначения:

  • индекс [math]\mathtt{P}[/math] — размерность массива из условия задачи,
  • [math]\mathtt{\odot}[/math] — та операция, которую мы считаем на данном многомерном дереве отрезков.

В нижеприведенном псевдокоде будет встречен [math]\varepsilon[/math] — нейтральный элемент.


Псевдокод:

void query(int area[], int x1, int x2, ..., int xP, int leftBorder, int rightBorder, int queryLeft, int queryRight, int node)
    if queryLeft > queryRight
        return [math]\varepsilon[/math]
    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) [math]\odot[/math]
           query(area[], x1, x2, ..., xP, med + 1, rightBorder, max(queryLeft, med + 1), queryRight, node * 2 + 2)

Обновление

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

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

Заметим, что "переходов к следующей координаты" при рассмотрении некоторой координатной оси будет совершено [math]\log n[/math], а итоговая сложность составит [math]O(\log^{p} n)[/math].

Отдельно следует рассмотреть, что происходит, когда текущее дерево является одномерным (мы рассмотрели все координаты, кроме текущей):

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

Псевдокод:

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] [math]\odot[/math] 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)

Построение

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

Псевдокод:

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] [math]\odot[/math] 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)

Заметим, что построение дерева требует [math]O(n)[/math] времени, где [math]n[/math] — общее число элементов в массиве.

См. также

Источники информации