1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Хранение==
[[Файл:SegmentTree2DExample.png|thumb|350px|right|Пример двумерного дерева отрезков для 16 элементов]]
Пусть необходимо хранить дерево отрезков для <tex>p</tex>-мерной области, размеры которой <tex>n_1 \times n_2 \times \ldots \times n_p</tex>. Удобнее всего это делать с помощью <tex>p</tex>-мерного массива. Однако его размеры по каждой координате, так же как и в одномерном случае, должны превышать размеры соответствующего отрезка в 4 раза. На самом деле нам нужно хранить <tex>2n</tex> чисел, но, если мы хотим, чтобы правый и левый сын некоторой вершины <tex>i</tex> находились на <tex> 2i + 1</tex> и <tex>2i + 2</tex> месте, то, если длина отрезка не является степенью двойки, некоторые элементы массива могут быть не задействованы, поэтому, в худшем случае, может понадобиться массив, размер которого в 4 раза превышает количество элементов. Т. е. потребуется массив размером <tex>4 n_1 \times 4 n_2 \times \ldots \times 4 n_p</tex>. Так двумерное дерево отрезков удобно хранить в виде массива, размером <tex>4N \times 4M</tex>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.
На рисунке справа показан пример дерева отрезков для суммы на массиве 4 на 4, заполненного числами от 1 от 16. Например, в элементе <tex>a[2][0] = 100</tex> хранится сумма элементов, соответствующих отрезку <tex>[2..3]</tex> по первой координате и <tex>[0..3]</tex> по второй в исходном массиве. А в ячейке <tex>a[0][0] = 136</tex> хранится сумма всех элементов.
Еще один момент, в которых отличается реализация {{---}} передаваемые в функцию параметры. В многомерном случае кроме всего прочего следует также передать рассматриваемое <tex>p-i+1</tex>-мерное дерево (или кортеж из чисел, указывающих на соответствующие элементы массива), а также область, которую следует рассматривать (или <tex>p-i+1</tex> пар чисел, обозначающих отрезки на соответствующих координатных осях). Все остальные детали реализации остаются такими же как и в одномерном дереве отрезков.
В каждом нижеприведенном псевдокоде будет встречено обозначение будут встречены обозначения:* индекс <tex>\mathtt{P}</tex> {{---}} размерность массива из условия задачи,* <tex>\mathtt{epsilon\odot}</tex> {{---}}та операция, которую мы считаем на данном многомерном дереве отрезков. В нижеприведенном псевдокоде будет встречен <tex>\varepsilon</tex> {{---}} нейтральный элемент.
'''void''' query('''int''' area[], '''int''' x1, '''int''' x2, ..., '''int''' xP, '''int''' leftBorder, '''int''' rightBorder, '''int''' queryLeft, '''int''' queryRight, '''int''' node)
'''if''' queryLeft > queryRight
'''return''' epsilon<tex>\varepsilon</tex>
'''if''' leftBorder == queryLeft '''and''' rightBorder == queryRight
'''if''' последняя координата
'''return''' query(area[], x1, x2, ..., xP, node, 0, m - 1, area[P + 2].left, area[P + 2].right, 0)
med = (leftBorder + rightBorder) / 2
'''return''' query(area[], x1, x2, ..., xP, leftBorder, med, queryLeft, min(queryRight, med), node * 2 + 1) <tex>\timesodot</tex>
query(area[], x1, x2, ..., xP, med + 1, rightBorder, max(queryLeft, med + 1), queryRight, node * 2 + 2)
</code>
'''for''' I = 1..n
'''if''' xILeft != xIRigth
t[x1][x2]...[xP][node] = t[x1][x2]...[xI * 2 + 1]...[node] <tex>\timesodot</tex> t[x1][x2]...[xI * 2 + 2]...[node]
'''return'''
t[x1][x2]...[xP][node] = newElem.value
==Построение==
Построение многомерного дерева отрезков практически ничем не отличается от его обновления. Единственное различие {{---}} если рассматриваемый отрезок состоит из более чем одного элемента, то необходимо рекурсивно вызываться из обоих обеих частей.
Псевдокод:
'''if''' последняя координата
'''for''' I = 1..n
'''if''' xILeft != xIRigthxIRight t[x1][x2]...[xP][node] = t[x1][x2]...[xI * 2 + 1]...[node] <tex>\timesodot</tex> t[x1][x2]...[xI * 2 + 2]...[node]
'''return'''
t[x1][x2]...[xP][node] = data[x1Left][x2Left]...[xPLeft][node]
