81
правка
Изменения
Нет описания правки
Рассмотрим отличия реализации многомерного и одномерного случаев. На самом деле, отличаются реализации только в двух местах. Во-первых, если рассматриваемый отрезок совпадает с необходимым, то в одномерном случае функция просто возвращает число, которое находится в текущем элементе массива. В многомерном случае, если рассматриваемая координата не последняя, следует вместо этого узнать значение, рекурсивно перейдя к следующей координате, и вернуть его.
Еще один момент, в которых отличается реализация {{---}} передаваемые в функцию параметры. В многомерном случае кроме всего прочего следует также передать рассматриваемое <tex>p-i+1</tex>-мерное дерево (или кортеж из чисел, указывающих на соответствующие элементы массива), а также область, которую следует рассматривать (или <tex>p-i+1</tex> пар чисел, обозначающих отрезки на соответствующих координатных осях). Все остальные детали реализации остаются такими же как и в одномерном дерево дереве отрезков.
Псевдокод:
'''if''' последняя координата
'''return''' t[x1][x2]...[xP][vertexnode]
'''else'''
'''return''' operationCalcquery(area[], x1, x2, ..., xP, vertexnode, 0, m - 1, area[P + 2].left, area[P + 2].right, 0)
med = (leftBorder + rightBorder) / 2
'''return''' operationCalcquery(area[], x1, x2, ..., xP, leftBorder, med, needLeftqueryLeft, min(needRightqueryRight, med), vertex node * 2 + 1) <tex>\times</tex> operationCalcquery(area[], x1, x2, ..., xP, med + 1, rightBorder, max(needLeftqueryLeft, med + 1), needRightqueryRight, vertex node * 2 + 2)
==Обновление==
Псевдокод:
update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, rightBorder, vertexnode)
'''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 node * 2 + 1)
'''else'''
update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, med + 1, rightBorder, vertex node * 2 + 2)
'''if''' последняя координата
'''for''' I = 1..n
'''if''' xILeft != xIRigth
t[x1][x2]...[xP][vertexnode] = t[x1][x2]...[xI * 2 + 1]...[vertexnode] <tex>\times</tex> t[x1][x2]...[xI * 2 + 2]...[vertexnode]
'''return'''
t[x1][x2]...[xP][vertexnode] = newElem.value
'''else'''
'''if''' leftBorder != rightBorder
update(newElem, x1, x2, ..., xP, vertexnode, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)
==Построение==
Псевдокод:
build(x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, rightBorder, vertexnode)
'''if''' leftBorder != rightBorder
med = (leftBorder + rightBorder) / 2
update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, leftBorder, med, vertex node * 2 + 1) update(newElem, x1, x2, ..., xP, x1Left, x1Right, x2Left, x2Right, ..., xPLeft, xPRight, med + 1, rightBorder, vertex node * 2 + 2)
'''if''' последняя координата
'''for''' I = 1..n
'''if''' xILeft != xIRigth
t[x1][x2]...[xP][vertexnode] = t[x1][x2]...[xI * 2 + 1]...[vertexnode] <tex>\times</tex> t[x1][x2]...[xI * 2 + 2]...[vertexnode]
'''return'''
t[x1][x2]...[xP][vertexnode] = data[x1Left][x2Left]...[xPLeft][vertexnode]
'''else'''
'''if''' leftBorder != rightBorder
update(newElem, x1, x2, ..., xP, vertexnode, x1Left, x1Rigth, x2Left, x2Right, ..., leftBorder, rightBorder, 0, m - 1, 0)
Заметим, что построение дерева требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} общее число элементов в массиве.
