81
правка
Изменения
многомерный случай
t[vertexX][vertexY] = t[vertexX][vertexY * 2 + 1] <tex>\times</tex> t[vertexX][vertexY * 2 + 2]
Подсчет суммы некоторой функции от элементов, лежащих в прямоугольной области:
// first call - sumX(0, 0, n - 1, leftX, rightX, leftY, rightY, t)
t[vertexX][vertexY] = t[vertexX][vertexY * 2 + 1] <tex>\times</tex> t[vertexX][vertexY * 2 + 2]
==Многомерный случай==
Рассмотрим, как изменяться функции при переходе к <tex>n</tex>-мерному случаю.
Например, для операции обновления дерева отрезков изменения будут следующими. В коде будут присутствовать <tex>n</tex> функций update (для каждой из координат). Реально будут только две различные реализации этих функций (первая, при нахождении необходимых листьев дерева, рекурсивно переходит к следующей координате, вторая {{---}} только возвращает значение из массива). Мы можем не писать <tex>n</tex> одинаковых реализаций в коде, но тогда дерево отрезков придется хранить не в <tex>n</tex>-мерном массиве, а в одномерном (это не сильно усложнит реализацию, но понятность кода уменьшится).
Рассмотрим более подробно устройство такой функции. В качестве параметров она должна принимать область, на которой считается операция, информацию о том, из каких ячеек массива мы рекурсивно спустились, отрезок, который обрабатывается по текущей координате и необходимый нам отрезок, а также номер текущей ячейки массива.
operationCalc(area[], x1, x2, ..., xP, leftBorder, rightBorder, needLeft, needRight, vertex)
Вначале следует проверить, что обрабатываемый отрезок не пустой (иначе вернуть нейтральный элемент для операции)
if leftBorder > rigthBorder
return 0
Потом, если текущий отрезок совпадает с искомым, необходимо перейти к поиску по следующей координате
if leftBorder == needLeft && rightBorder == needRight
return operationCalc(area[], x1, x2, ..., xP, vertex, 0, m - 1, area[P + 2].left, area[P + 2].right, 0)
Если же отрезок не совпадает, то делим его пополам и рекурсивно вызываемся от его частей
med = (leftBorder + rightBorder) / 2
return operationCalc(area[], x1, x2, ..., xP, leftBorder, med, needLeft, min(needRight, med), vertex * 2 + 1) <tex>\times</tex>
operationCalc(area[], x1, x2, ..., xP, med + 1, rightBorder, max(needLeft, med + 1), needRight, vertex * 2 + 2)
В реализации для последней координаты вместо рекурсивного перехода следует вернуть значение из массива
if leftBorder == needLeft && rightBorder == needRight
return t[x1][x2]...[xP][vertex]
Теперь рассмотрим операцию обновления. По аналогии напишем <tex>n</tex> функций, в каждой из которых сделаем следующее:
* Если рассматриваемый отрезок содержит больше одного элемента, разобьем его на две части и рекурсивно перейдем в ту, где находится необходимый элемент
* Перейдем к следующей координате или обновим массив (для последней координаты)
Псевдокод:
update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, rightBorder, vertex)
if leftBorder == rightBorder
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
update(newElem, x1, x2, ..., xP, vertex, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)
else
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)
update(newElem, x1, x2, ..., xP, vertex, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)
==Источники==
