Викиконспекты - Вклад участника [ru]

Реализация запроса в дереве отрезков снизу

2012-06-06T15:43:22Z

95.26.124.164:

[[Файл:Down-up2.png‎|right|255px|thumb|Реализация запроса снизу вверх]]

==Алгоритм==

Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности.

[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие листья. Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. Аналогично действуем с элементом попавшим на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Продолжаем до тех пор, пока границы не пересекутся. Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат, иначе {{---}} ничего делать не надо.

==Псевдокод==

Пусть ассоциативная операция, над которой построено дерево отрезков, обозначается a <tex> \circ </tex> b, а результат считаем на отрезке [left, right]. При этом значения передающиеся в функцию left и right должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья).

query(left, right)
result = neutral; // Присваиваем результату значение нейтрального элемента (например для поиска суммы надо присвоить значение 0)
'''while''' left < right // Выполняем цикл до тех пор, пока левая и правая граница не пересекутся
'''if''' left mod 2 == 0 // Проверяем, является ли левая граница правым сыном (индексация с 0)
result = result <tex> \circ </tex> data[left]; // Если является, то пересчитаем результат и перенесем левую границу
left = left div 2;
'''else'''
left = left div 2; // Если не является, то установим границу на родительский элемент текущей границы
'''if''' right mod 2 == 1 // Аналогично проделываем операции с правой границей
result = result <tex> \circ </tex> data[right];
right = (right - 2) div 2;
'''else'''
right = (right - 2) div 2;
'''if''' left == right // После окончания цикла проверяем совпали ли границы
result = result <tex> \circ </tex> data[left]; // Если надо пересчитываем результат
'''return''' result;

==Ссылки==

[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]

[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков]

[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]

[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Дерево отрезков]]

Реализация запроса в дереве отрезков снизу

2012-06-06T15:29:26Z

95.26.124.164:

[[Файл:Down-up2.png‎|right|255px|thumb|Реализация запроса снизу вверх]]

==Алгоритм==

Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности.

[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие листья. Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. Аналогично действуем с элементом попавшим на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Продолжаем до тех пор, пока границы не пересекутся. Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат, иначе {{---}} ничего делать не надо.

==Псевдокод==

Пусть ассоциативная операция, над которой построено дерево отрезков, обозначается a <tex> \circ </tex> b, а результат считаем на отрезке [left, right]. При этом значения передающиеся в функцию left и right должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья).

query (left, right)
result = neutral; // Присваиваем результату значение нейтрального элемента (например для поиска суммы надо присвоить значение 0)
'''while''' left < right // Выполняем цикл до тех пор, пока левая и правая граница не пересекутся
'''if''' left mod 2 == 0 // Проверяем, является ли левая граница правым сыном (индексация с 0)
result = result <tex> \circ </tex> data[left]; // Если является, то пересчитаем результат и перенесем левую границу
left = left div 2;
'''else'''
left = left div 2; // Если не является, то установим границу на родительский элемент текущей границы
'''if''' right mod 2 == 1 // Аналогично проделываем операции с правой границей
result = result <tex> \circ </tex> data[right];
right = (right - 2) div 2;
'''else'''
right = (right - 2) div 2;
'''if''' left == right // После окончания цикла проверяем совпали ли границы
result = result <tex> \circ </tex> data[left]; // Если надо пересчитываем результат
'''return''' result;

==Ссылки==

[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]

[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков]

[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]

[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Дерево отрезков]]