Многомерное дерево отрезков

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

Структура

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

Двумерное дерево отрезков

Рассмотрим следующую задачу.

Задача:

Дано поле размером [math]N \times M[/math], заполненное некоторыми числами. Необходимо уметь обрабатывать два типа запросов: Изменить некоторый элемент Посчитать значение некоторой ассоциативной функции [math]\times[/math] на прямоугольной области

Хранение

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

Двумерное дерево отрезков удобно хранить в виде массива, размером [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] — общее количество элементов.

Псевдокод для двумерного случая

Построение:

// 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] [math]\times[/math] 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] [math]\times[/math] 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 > 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) [math]\times[/math]
        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) [math]\times[/math]
        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] [math]\times[/math] 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] [math]\times[/math] t[vertexX][vertexY * 2 + 2]   

Источники

• Дерево отрезков — e-maxx.ru
• Двумерное дерево отрезков — habrahabr.ru

См. также

• Дерево отрезков. Построение
• Сжатое многомерное дерево отрезков
• Многомерное дерево Фенвика