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

Обсуждение:Реализация запроса в дереве отрезков сверху

2012-04-30T05:47:03Z

109.188.169.214:

: {{tick | ticked=1}} описание перенести в шапку статьи
: {{tick | ticked=1}} зачем какое-то тире перед началом ссылки в разделе «Ссылки».
: {{tick}} А почему в описании алгоритма одни интервалы полуоткрытые, а другие — закрытые?
: {{tick}} не надо объяснять алгоритм на примере RSQ, объясняй на примере абстрактной операции с деревом отрезков. Вот уже в примере работы — ок, пусть будет RSQ.
:: «возвращаем нулевое значение» — это совсем не абстрактно.
:: «как некоторую функцию» — почему «некоторую»?
: {{tick | ticked=1}} обычно вершина в дереве отрезков — node, vertex (у тебя же от этого название «ver» образовано?) — ближе к графам.
: {{tick | ticked=1}} Псевдокод надо делать как можно абстрактнее. Зачем передавать в рекурсию левую и правую границу отрезка, если ты уже передаешь ver? Левую и правую границу можно получить как tree[ver].left, tree[ver].right, значение — как tree[ver].value. И почитай правила оформления псевдокода. Можно вообще передавать в рекурсии node, тогда не нужны будут вот эти ver * 2 и ver * 2 + 1, можно будет вызываться от node.left, node.right.
: {{tick | ticked=1}} ver * 2 и ver * 2 + 1 — неправильно, так как мы все-таки используем 0-индексацию, а 0 * 2 == 0
: {{tick | ticked=1}} Отрезки в псевдокоде должны быть полуотурытыми, иначе он у тебя может входить в бесконечную рекурсию. (l=k, r=k => m = k, дальше опять вызов от l=k, r=k).
: {{tick}} => смотрится фигово, лучше в техе хотя бы. И названия вершин (1, 2 и т.д.) там в техе пиши. еще в примере в одном месте форматирование поехало.
:: '''не исправлено'''
: {{tick | ticked=1}} Тут надо просто все нормально переписать, а то как-то обрывисто. Добавить интервики, категории. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 00:08, 7 февраля 2012 (MSK)
: {{tick}} какие-то странные опечатки и фразы
:: `«причем левые границы обоих отрезков - включительно, а правые — нет»
:: «Текущий полуинтервал совпадает, то возвращаем»
:: «Используем в реализаций полуинтервалы»
:: «каждый полуинтервал разбивается не более, чем на O(log n) полуинтервал»

Обсуждение:Реализация запроса в дереве отрезков сверху

2012-04-30T05:44:18Z

109.188.169.214:

: {{tick | ticked=1}} описание перенести в шапку статьи
: {{tick | ticked=1}} зачем какое-то тире перед началом ссылки в разделе «Ссылки».
: {{tick}} А почему в описании алгоритма одни интервалы полуоткрытые, а другие — закрытые?
: {{tick}} не надо объяснять алгоритм на примере RSQ, объясняй на примере абстрактной операции с деревом отрезков. Вот уже в примере работы — ок, пусть будет RSQ.
: {{tick | ticked=1}} обычно вершина в дереве отрезков — node, vertex (у тебя же от этого название «ver» образовано?) — ближе к графам.
: {{tick | ticked=1}} Псевдокод надо делать как можно абстрактнее. Зачем передавать в рекурсию левую и правую границу отрезка, если ты уже передаешь ver? Левую и правую границу можно получить как tree[ver].left, tree[ver].right, значение — как tree[ver].value. И почитай правила оформления псевдокода. Можно вообще передавать в рекурсии node, тогда не нужны будут вот эти ver * 2 и ver * 2 + 1, можно будет вызываться от node.left, node.right.
: {{tick | ticked=1}} ver * 2 и ver * 2 + 1 — неправильно, так как мы все-таки используем 0-индексацию, а 0 * 2 == 0
: {{tick | ticked=1}} Отрезки в псевдокоде должны быть полуотурытыми, иначе он у тебя может входить в бесконечную рекурсию. (l=k, r=k => m = k, дальше опять вызов от l=k, r=k).
: {{tick}} => смотрится фигово, лучше в техе хотя бы. И названия вершин (1, 2 и т.д.) там в техе пиши. еще в примере в одном месте форматирование поехало.
:: '''не исправлено'''
: {{tick | ticked=1}} Тут надо просто все нормально переписать, а то как-то обрывисто. Добавить интервики, категории. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 00:08, 7 февраля 2012 (MSK)
: {{tick}} какие-то опечатки
:: «Используем в реализаций полуинтервалы»
:: «каждый полуинтервал разбивается не более, чем на O(log n) полуинтервал»

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

2012-04-30T05:25:33Z

109.188.169.214:

Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.

==Алгоритм==
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на отрезке <tex>[a .. b]</tex>.
[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков]]

Будем передавать в качестве параметров рекурсий следующие переменные:
* <tex>node</tex> {{---}} номер(в массиве с деревом отрезков) текущей вершины дерева.
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого отрезка.

Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы отрезков, за которые "отвечает" наша вершина, причем левые границы обоих отрезков - включительно, а правые - нет. В дальнейшем будем называть подобную структуру полуинтвервалом.

Запустим рекурсивную процедуру от всего отрезка(то есть от корневой вершины).

Для текущего состояния проверяем следующие условия :

* Если текущий полуинтервал не пересекается с искомым, то возвращаем нулевое значение.
''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;

* Текущий полуинтервал совпадает, то возвращаем значение в текущей вершине.
''Например'': текущий и искомый <tex>[2..4)</tex>;

* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом в зависимости от типа запроса возвращаем значение на текущем отрезке, как некоторую функцию от результатов выполнения на детях.
''Замечание:''

При передаче новых параметров следует изменять не только границы, за которые отвечает текущая вершина, но и границы запрашиваемого полуинтервала, чтобы на последующих шагах произошло полное совпадение полуинтервалов.

Так как каждый полуинтервал разбивается не более, чем на <tex>O(\log n)</tex> полуинтервал (поскольку на каждом уровне дерева может быть не более двух полуинтервалов из разбиения, а всего уровней <tex>\log n</tex> ), то данная реализация выполняется за <tex>O(\log n)</tex>.

==Пример==
Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммы на отрезке).

При этом сумма на текущем отрезке (в случае вызова рекурсий от детей) равна сумме результатов выполнения операций на этих детях.

Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма - это отрезок <tex>[1 .. 4]</tex>( полуинтервал <tex>[1 .. 5)</tex>).

Рассмотрим данную рекурсию:

*Текущий полуинтервал <tex>[0 .. 8)</tex>, он больше <tex>[1 .. 5)</tex> => переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex>

*<tex>[0 .. 4)</tex> выходит за границы<tex> [1 .. 5)</tex>, <tex>[4 .. 8)</tex> выходит за границы <tex>[1 .. 5)</tex> => переходим по рекурсивным вызовам на <tex>[0 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 6)</tex>, <tex>[6 .. 8)</tex>.

*<tex>[0 .. 2)</tex> выходит за границы <tex>[1 .. 5)</tex> => переходим в листья <tex>0, 1 </tex>; <tex>[2 .. 4)</tex> целиком внутри <tex>[1 .. 5)</tex> => возвращаем значение в <tex>[2 .. 4)</tex>; <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5)</tex> => возвращаем нулевое значение; <tex>[4 .. 6)</tex> выходит за границы <tex>[1 .. 5)</tex> => переходим к листьям <tex>4</tex> и <tex>5</tex>.

*листья <tex>5</tex> и <tex>0</tex> не пересекается с полуинтервалом <tex>[1 .. 5)</tex> => возвращаем нулевое значение, а листья <tex>4</tex> и <tex>1</tex> целиков внутри <tex>[1 .. 5)</tex> => возвращаем значения в этих листьях.

==Реализация==
Рассмотрим реализацию задачи RSQ.
<code>

int get_sum (int node, int a, int b)
{
// Используем в реализаций полуинтервалы

l = tree[node].left;
r = tree[node].right;
if [l, r) <tex>\bigcap</tex> [a, b) == <tex> \varnothing</tex>
return 0;
if [l, r) == [a, b)
return tree[node];
int m = (l + r) / 2;
return get_sum (node * 2 + 1, a, min(b, m))
+ get_sum (node * 2 + 2, max(a, m), b);
}
</code>

==Ссылки==

[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 Визуализатор дерева отрезков]

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