Изменения

[[Дерево отрезков. Построение|Дерево отрезков]] можно обобщить в естественным образом обобщается на двумерный и вообще говоря многомерный случай для решения таких задач. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике за <tex>O(\log^{p} n)</tex>, где <tex>p</tex> {{---}} размерность пространства, а <tex>n</tex> {{---}} ширина гиперкуба на котором производятся вычисления. ==Структура==<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> и получим необходимую асимптотику. ==Двумерное дерево отрезков==Поскольку в большинстве случаев на практике используются деревья отрезков размерности не более 2, а также для облегчения понимания далее будут рассматриваться только двумерные деревья отрезков. Рассмотрим следующую задачу.

Рассматривается задача регионального поиска. Задано множество точек в Дано поле размером <tex>pN \times M</tex>-мерном евклидовом пространстве, заполненное некоторыми числами. Образцом для поиска является гиперпрямоугольная область. Найти Необходимо уметь обрабатывать два типа запросов: * Изменить некоторый элемент* Посчитать сумму/минимум/максимум.на прямоугольной области

==ПостроениеХранение==Пусть задано [[Файл:SegmentTree2DExample.png|thumb|250px|right|Пример двумерного дерева отрезков для 16 элементов]]Двумерное дерево отрезков удобно хранить в виде массива, размером <tex>p4N \times 4M</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3.Каждая строчка такого массива соответствует некоторому отрезку по первой координате.Сама же строчка является деревом отрезков по второй координате.x_p</tex>. Т.к. при построении одномерного  На рисунке справа показан пример дерева, индексы отрезков для массива разбиваются 4 на отрезки4, заполненного числами от 1 от 16. Например, тогда при построении многомерного дерева координаты будут обрабатываться сначала по в элементе <tex>x_1 a[2][0] = 100</tex>хранится сумма элементов, затем по соответствующих отрезку <tex>x_2</tex> и так далее[2... Далее дерево строится рекурсивно: далее координаты по <tex>x_13]</tex> обрабатываем по координатам первой координате и <tex>x_2[0..3]</tex>, по второй в исходном массиве. А в ячейке <tex>x_3a[0][0] = 136</tex> (по всем возможным координатам) и далее по аналогии... То есть получается, что основная идея построения многомерного дерева отрезков - вкладывание деревьев отрезка друг в другахранится сумма всех элементов.

Пример задачиИнтересно, в которой удобно использовать многомерное что если построить дерево отрезков==Пример двумерного дерева==Рассмотрим процесс построения предельного случая при <tex>p = 2</tex>вначале по второй координате, а потом по первой, то получившийся массив будет таким же. Т.Пусть задан е. данный двумерный массив элементов размера <tex>n \times m</tex>. Упорядочим можно рассматривать как массив деревьев отрезов, где каждое дерево соответствует некоторому отрезку по первой второй координате и построим на , а в нем дерево отрезков. После этого для каждого узла дерева строим еще одно дерево отрезков хранятся суммы по координате <tex>y</tex>, которые находятся на том же отрезкепервой.

К примеруЗаметим,двумерное дерево размером что в общем случае для хранения <tex>p</tex>-мерного дерева отрезков требуется <tex>4 \times 4 :^p n</tex> памяти, где <tex>n</tex>{{---}} общее количество элементов.

==Псевдокод==Построение: // 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][Файл:Многомерное до.jpgly] 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][Файл:До хранение.JPG]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Структура использует <tex>O my = (n^ply + ry)</tex> памяти, и отвечает на запрос за 2 if y <tex>O= my updateY(log^{p} nvx, lx, rx, vy * 2 + 1, ly, my, x, y, val, t)</tex> else updateY(vx, lx, rx, vy * 2 + 2, my + 1, ry, x, y, val, где <tex>p</tex>-размерность дерева.t) t[vx][vy] = t[vx][vy * 2 + 1] + t[vx][vy * 2 + 2]

*e-maxx.ru: [http://e-maxx.ru/algo/segment_tree Дерево отрезков{{---}} e-maxx.ru] <br/>*F. P. Preparata, M.I. Shamos - Вычислительная геометрия [http://pogorskiy.narodhabrahabr.ru/rectqpost/131072/)/ Двумерное дерево отрезков {{---}} habrahabr.htm Главы о региональном поискеru]

*[[Дерево отрезков. Построение]] <br/>*[[Сжатое многомерное дерево отрезков]] <br/>*[[Многомерное дерево Фенвика]] <br/> [[Категория: Дискретная математика и алгоритмы]][[Категория: Дерево отрезков]]