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

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

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

Поскольку в большинстве случаев на практике используются деревья отрезков размерности не более 2, а также для облегчения понимания далее будут рассматриваться только двумерные деревья отрезков. Рассмотрим следующую задачу.

Задача:

Дано поле размером [math]N \times M[/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 - массив дерева отрезков
// [lx, rx) - полуинтервал

buildX(vx, lx, rx, a[][], t[][])
 if lx != rx
   mx = (lx + rx + 1) / 2
   buildX(vx * 2 + 1, lx, mx, a, t)
   buildX(vx * 2 + 2, mx, rx, a, t)
 buildY(vx, lx, rx, 0, 0, m, a, t);

buildY(vx, lx, rx, vy, ly, ry, a[][], t[][])
 if ly == ry
   if lx == rx
     t[vx][vy] = a[lx][ly] 
   else
     t[vx][vy] = t[vx * 2 + 1][vy] + t[vx * 2 + 2][vy];
 else
   my = (ly + ry + 1) / 2
   buildY(vx, lx, rx, vy * 2 + 1, ly, my, a, t)
   buildY(vx, lx, rx, vy * 2 + 2, my, ry, a, t)
   t[vx][vy] = t[vx][vy * 2 + 1] + t[vx][vy * 2 + 2]

Подсчет суммы элементов:

// first call - sumX(0, 0, n - 1, lx, rx, ly, ry, t)

sumX(vx, tlx, trx, lx, rx, ly, ry, t[][])
 if lx > rx
  return 0
 if lx == tlx && rx == trx
  return sumY(vx, 0, 0, m - 1, ly, ry)
 tmx = (tlx + trx) / 2
 return sumX(vx * 2 + 1, tlx, tmx, lx, min(rx, tmx), ly, ry, t) +
        sumX(vx * 2 + 2, tmx + 1, trx, max(lx, tmx + 1), rx, ly, ry, t)

sumY(vx, vy, tly, try, ly, ry)
 if ly > ry
  return 0
 if ly == tly && ry == try
  return t[vx][vy]
 tmy = (tly + try) / 2
 return sumY(vx, vy * 2 + 1, tly, tmy, ly, min(ry, tmy), t) +
        sumY(vx, vy * 2 + 2, tmy + 1, try, max(ly, tmy + 1), ry, t)

Обновление элемента:

// first call - updateX(0, 0, n - 1, x, y, val, t)

updateX(vx, lx, rx, x, y, val, t[][])
 if lx != rx
  mx = (lx + rx) / 2
  if x <= mx
   updateX(vx * 2 + 1, lx, mx, x, y, val, t)
  else
   updateX(vx * 2 + 2, mx + 1, rx, x, y, val, t)
 updateY(vx, lx, rx, 0, 0, m - 1, x, y, val, t)

updateY(vx, lx, rx, vy, ly, ry, x, y, val, t[][])
 if ly == ry
  if lx == rx
   t[vx][vy] = val
  else
   t[vx][vy] = t[vx * 2 + 1][vy] + t[vx * 2 + 2][vy]
 else
  my = (ly + ry) / 2
  if y <= my
   updateY(vx, lx, rx, vy * 2 + 1, ly, my, x, y, val, t)
  else
   updateY(vx, lx, rx, vy * 2 + 2, my + 1, ry, x, y, val, t) 
  t[vx][vy] = t[vx][vy * 2 + 1] + t[vx][vy * 2 + 2]   

Источники

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

См. также

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