Редактирование: Многомерное дерево отрезков

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 18: Строка 18:
 
==Хранение==
 
==Хранение==
 
[[Файл:SegmentTree2DExample.png|thumb|350px|right|Пример двумерного дерева отрезков для 16 элементов]]
 
[[Файл: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>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.
+
Пусть необходимо хранить дерево отрезков для <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> хранится сумма всех элементов.
 
На рисунке справа показан пример дерева отрезков для суммы на массиве 4 на 4, заполненного числами от 1 от 16. Например, в элементе <tex>a[2][0] = 100</tex> хранится сумма элементов, соответствующих отрезку <tex>[2..3]</tex> по первой координате и <tex>[0..3]</tex> по второй в исходном массиве. А в ячейке <tex>a[0][0] = 136</tex> хранится сумма всех элементов.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: