Изменения

Пусть необходимо хранить дерево отрезков для <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>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.