==Запрос==
Рассмотрим отличия реализации многомерного и одномерного случаев. На самом деле, отличаются реализации только в двух местах. Во-первых, если рассматриваемый отрезок совпадает с необходимым, то в одномерном случае функция просто возвращает число, которое находится в текущем элементе массива. В многомерном случае, если рассматриваемая координата не последняя, следует вместо этого узнать значение, рекурсивно перейдя к следующей координате, и вернуть его.
Еще один момент, в которых отличается реализация {{---}} передаваемые в функцию параметры. В многомерном случае кроме всего прочего следует также передать рассматриваемое <tex>p-i+1</tex>-мерное дерево (или картеж из чисел, указывающих на соответствующие элементы массива), а также область, которую следует рассматривать (или <tex>p-i+1</tex> пар чисел, обозначающих отрезки на соответствующих координатных осях). Все остальные детали реализации остаются такими же как и в одномерном дерево отрезков.
Псевдокод:
operationCalc(area[], x1, x2, ..., xP, leftBorder, rightBorder, needLeft, needRight, vertex)
if needLeft > needRight
return 0 // нейтральный элемент по операции <tex>\times</tex>
if leftBorder == needLeft && rightBorder == needRight
if последняя координата
return t[x1][x2]...[xP][vertex]
else
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 != rightBorder
update(newElem, x1, x2, ..., xP, vertex, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)
==Многомерный случай==
Рассмотрим, как изменяться функции при переходе к <tex>n</tex>-мерному случаю.
Например, для операции обновления дерева отрезков изменения будут следующими. В коде будут присутствовать <tex>n</tex> функций update (для каждой из координат). Реально будут только две различные реализации этих функций (первая, при нахождении необходимых листьев дерева, рекурсивно переходит к следующей координате, вторая {{---}} только возвращает значение из массива). Мы можем не писать <tex>n</tex> одинаковых реализаций в коде, но тогда дерево отрезков придется хранить не в <tex>n</tex>-мерном массиве, а в одномерном (это не сильно усложнит реализацию, но понятность кода уменьшится).
Рассмотрим более подробно устройство такой функции. В качестве параметров она должна принимать область, на которой считается операция, информацию о том, из каких ячеек массива мы рекурсивно спустились, отрезок, который обрабатывается по текущей координате и необходимый нам отрезок, а также номер текущей ячейки массива.
operationCalc(area[], x1, x2, ..., xP, leftBorder, rightBorder, needLeft, needRight, vertex)
Вначале следует проверить, что обрабатываемый отрезок не пустой (иначе вернуть нейтральный элемент для операции)
if needLeft > needRight
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]
==Источники==
