Многомерное дерево отрезков
Дерево отрезков естественным образом обобщается на двумерный и вообще говоря многомерный случай. Такая структура данных может вычислять значение некоторой ассоциативной функции на гиперпрямоугольнике за , где — размерность пространства, а — ширина гиперкуба на котором производятся вычисления.
Структура
-мерное дерево отрезков — обычное дерево отрезков, элементами которого являются деревья отрезков размерности на 1 меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано -мерное пространство с координатными осями . Необходимо вычислять некоторую ассоциативную функцию на гиперпрямоугольнике. Для этого сначала найдем элементы дерева, соответствующие координате. Для каждого из этих элементов рекурсивно перейдем в соответствующие им деревья отрезков и в них найдем элементы, отвечающие соответствующим координатам исходной гиперпрямоугольной области, и т. д. Таким образом, алгоритм совершит вхождений в рекурсию, каждая итерация которой работает за и получим необходимую асимптотику.
Двумерное дерево отрезков
Поскольку в большинстве случаев на практике используются деревья отрезков размерности не более 2, а также для облегчения понимания далее будут рассматриваться только двумерные деревья отрезков. Рассмотрим следующую задачу.
| Задача: |
Дано поле размером , заполненное некоторыми числами. Необходимо уметь обрабатывать два типа запросов:
|
Хранение
Двумерное дерево отрезков удобно хранить в виде массива, размером . Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.
На рисунке справа показан пример дерева отрезков для массива 4 на 4, заполненного числами от 1 от 16. Например, в элементе хранится сумма элементов, соответствующих отрезку по первой координате и по второй в исходном массиве. А в ячейке хранится сумма всех элементов.
Интересно, что если построить дерево вначале по второй координате, а потом по первой, то получившийся массив будет таким же. Т. е. данный двумерный массив можно рассматривать как массив деревьев отрезков, где каждое дерево соответствует некоторому отрезку по второй координате, а в нем хранятся суммы по первой.
Заметим, что в общем случае для хранения -мерного дерева отрезков требуется памяти, где — общее количество элементов.
Псевдокод
Построение:
// 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]
