Изменения

[[Файл:SegmentTreeWorking.png|thumb|450px600px|right|Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)]]

[[Файл:SegmentTree2DExample.png|thumb|250px350px|right|Пример двумерного дерева отрезков для 16 элементов]]Пусть необходимо хранить дерево отрезков для <tex>p</tex>-мерной области, размеры которой <tex>n_1 \times n_2 \times ... \times n_p</tex>. Удобнее всего это делать с помощью <tex>p</tex>-мерного массива. Однако его размеры по каждой координате, так же как и в одномерном случае, должны превышать размеры соответствующего отрезка в 4 раза. На самом деле нам нужно хранить <tex>2n</tex> чисел, но если мы хотим, чтобы правый и левый сын некоторой вершины <tex>i</tex> находились на <tex> 2i + 1</tex> и <tex>2i + 2</tex> месте, то если длина отрезка не является степенью двойки, некоторые элементы массива могут быть не задействованы. Т. е. потребуется массив размером <tex>4 n_1 \times 4 n_2 \times ... \times 4 n_p</tex>. Так двумерное дерево отрезков удобно хранить в виде массива, размером <tex>4N \times 4M</tex>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.

Еще один момент, в которых отличается реализация {{---}} передаваемые в функцию параметры. В многомерном случае кроме всего прочего следует также передать рассматриваемое <tex>p-i+1</tex>-мерное дерево (или картеж кортеж из чисел, указывающих на соответствующие элементы массива), а также область, которую следует рассматривать (или <tex>p-i+1</tex> пар чисел, обозначающих отрезки на соответствующих координатных осях). Все остальные детали реализации остаются такими же как и в одномерном дерево отрезков.

'''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 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, rightBorder, 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

update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, med + 1, rightBorder, 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)

med = (leftBorder + rightBorder) / 2 update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, med, vertex * 2 + 1) update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, med + 1, rightBorder, 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] = data[x1Left][x2Left]...[xPLeft][vertex] '''else''' '''if''' leftBorder != rightBorder update(newElem, x1, x2, ..., xP, vertex, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)