81
правка
Изменения
Нет описания правки
Функция, вычисляющая ответ, должна работать следующим образом. На вход она принимает <tex>i</tex>-мерное дерево отрезков, которое соответствует рассматриваемой области (где <tex>i</tex> {{---}} количество координатных осей, которые не были рассмотрены), а также <tex>i</tex>-мерную область, для которой следует вычислить функцию. Вначале она находит <tex>i-1</tex>-мерные деревья отрезков, которые соответствуют отрезку по <tex>p-i+1</tex> координате, и рекурсивно запускается от них (если текущее дерево одномерное, то функция просто возвращает ответ из соответствующего листа). После этого считает итоговый результат, используя полученные после рекурсивных вызовов значения.
Для того, чтобы определить, от каких именно деревьев отрезков следует запускаться рекурсивно, действовать необходимо так же, как и в одномерном случае. Т. е. если текущий отрезок не пересекается с необходимым, то возвращаем нейтральный элемент, если он полностью лежит в необходимом отрезке, то рекурсивно переходим к следующей размерностикоординате, иначе разобьем текущий отрезок пополам, и рассмотри отдельно каждую из частей.
На рисунке справа показан пример обработки очередной координаты (поиск соответствующих отрезку элементов {{---}} деревьев на 1 меньшей мерности).
Заметим, что в общем случае для хранения <tex>p</tex>-мерного дерева отрезков требуется <tex>4^p n</tex> памяти, где <tex>n</tex> {{---}} общее количество элементов.
==Построение==
==Запрос==
==Обновление==
Как и в одномерном случае, обновить в массиве необходимо не один элемент, а все, которые отвечают за области, в которых он присутствует. Таким образом, при обработке отрезка по некоторой координате (если она не последняя) следует выполнить следующие действия:
* Если рассматриваемый отрезок содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент
* Перейдем к следующей координате
Заметим, что "переходов к следующей координаты" при рассмотрении некоторой координатной оси будет совершено <tex>\log n</tex>, а итоговая сложность составит <tex>O(\log^{p} n)</tex>.
Отдельно следует рассмотреть, что происходит, когда текущее дерево является одномерным (мы рассмотрели все координаты, кроме текущей):
* Если рассматриваемый отрезок содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент
* Найдем первую координату, в которой рассматривается больше одного элемента. Обновим значение элемента массива с помощью уже вычисленных значений для разбитого надвое отрезка по этой координате.
* Если мы рассматриваем область, состоящую из одного элемента, обновим значение массива.
Псевдокод:
update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, rightBorder, vertex)
'''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, vertex * 2 + 1)
'''else'''
update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, med + 1, vertex * 2 + 2)
'''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'''
'''if''' leftBorder != rightBorder
update(newElem, x1, x2, ..., xP, vertex, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)
==Многомерный случай==
return t[x1][x2]...[xP][vertex]
==Источники==
