81
правка
Изменения
Нет описания правки
Заметим, что в общем случае для хранения <tex>p</tex>-мерного дерева отрезков требуется <tex>4^p n</tex> памяти, где <tex>n</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)
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
update(newElem, x1, x2, ..., xP, vertex, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)
==Построение==
Построение многомерного дерева отрезков практически ничем не отличается от его обновления. Единственное различие {{---}} если рассматриваемый отрезок состоит из более чем одного элемента, то необходимо рекурсивно вызываться из обоих частей.
Псевдокод:
build(x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, rightBorder, vertex)
'''if''' leftBorder != rightBorder
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)
Заметим, что построение дерева требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} общее число элементов в массиве.
==Источники==
* [http://e-maxx.ru/algo/segment_tree Дерево отрезков {{---}} e-maxx.ru]
