81
правка
Изменения
Новая страница: «== Определение == Priority Search Tree позволяет решать следующую задачу. Даны <tex>n</tex> точек, а такж...»
== Определение ==
Priority Search Tree позволяет решать следующую задачу. Даны <tex>n</tex> точек, а также запросы. Каждый запрос характеризуется отрезком по одной координате <tex>[y_1, y_2]</tex>, а также числом <tex>x_q</tex> по другой координате. Для каждого запроса структура возвращает все точки, которые находятся в отрезке <tex>[y_1, y_2]</tex> по одной координате, и имеют другую координату не больше <tex>x_q</tex>. На каждый запрос дерево отвечает за <tex>O(\log\,n + k)</tex>, где <tex>k</tex> {{---}} количество точек в ответе.
== Как строится? ==
Дерево строится рекурсивно. Выберем точку с наименьшей <tex>x</tex>-координатой (если таких несколько, то из них выберем с наименьшим <tex>y</tex>). Все остальные точки отсортируем по <tex>y</tex> и разобьем на две равные (количество может отличаться на один) части. Далее будем считать, что все точки первой части имеют координату <tex>y</tex> меньше всех точек второй части (с одинаковыми <tex>y</tex> поступаем как обычно {{---}} сравниваем по <tex>x</tex>). Для каждого из двух множеств, если оно не пусто, построим дерево рекурсивно.
{{Теорема
|statement=
PST занимает <tex>O(n)</tex> памяти.
|proof=
Каждая точка будет корнем ровно одного дерева. Количество деревьев не превышает количества точек. В сумме <tex>O(n)</tex>.
}}
{{Теорема
|statement=
Максимальная глубина PST <tex>O(\log\,n)</tex>.
|proof=
При рекурсивном вызове количество точек уменьшается как минимум в два раза.
}}
{{Теорема
|statement=
Построение PST работает за <tex>O(n\log\,n)</tex> времени.
|proof=
Необходимо отсортировать точки по <tex>y</tex> {{---}} для этого необходимо <tex>O(n\log\,n)</tex>. Построение каждого дерева требует <tex>O(k)</tex>, где <tex>k</tex> {{---}} количество точек в дереве, чтобы найти минимальную по <tex>x</tex> точку, а также для построения новых списков точек для сыновей. На каждом уровне <tex>O(n)</tex> точек, уровней <tex>O(\log\,n)</tex>, значит, в сумме тоже <tex>O(n\log\,n)</tex>.
}}
== Как отвечать на запрос? ==
Если <tex>x</tex> корня больше <tex>x_q</tex>, то никакие точки дерева не могут быть в ответе. Будем хранить также минимальную и максимальную по <tex>y</tex> точки, которые лежат в поддереве. Тогда, если отрезок запроса по <tex>y</tex> не пересекается с отрезком по <tex>y</tex> всех точек поддерева, то также никакие точки из дерева не должны быть добавлены в ответ. Если корень дерева лежит в нужном интервале, добавим его в ответ. Вызовем рекурсивно поиск ответа для двух сыновей.
{{Теорема
|statement=
Будет получен правильный ответ на запрос.
|proof=
Вроде бы очевидно.
}}
{{Теорема
|statement=
Ответ на запрос работает за <tex>O(\log\,n+k)</tex>, где <tex>k</tex> {{---}} размер ответа.
|proof=
Тут все сложнее. Представим, что мы ищем <tex>y_1</tex> и <tex>y_2</tex> (из запроса) в PST как в обычном дереве поиска по <tex>y</tex>. Рассмотрим все точки, которые лежат между двумя путями поиска. Среди них рассмотрим точки с <tex>x <= x_q</tex>. Ровно эти точки и есть ответ. Разобьем все вершины на три группы. Первая {{---}} вершины, которые лежат хотя бы на одном из двух путей. Их <tex>O(\log\,n)</tex>. Вторая {{---}} вершины, которые находятся между двумя путями. Третья {{---}} все остальные. Время обработки вершин первой группы не превышает <tex>O(\log\,n)</tex>. Как только мы зашли в вершину третей группы, сразу поймем, что отрезок по <tex>y</tex> не пересекается с запросом и выйдем. А зайти в них мы можем только из вершин, которые лежат на двух путях (а их <tex>O(\log\,n)</tex>). Отлично! Зайдя в вершину второй группы, мы либо ее добавим в ответ и продолжим, либо выйдем, так как единственная причина, почему корень не подошел {{---}} его <tex>x</tex> слишком большой, а, значит, и все вершины поддерева не подходят. В итоге их обработка занимает <tex>O(k)</tex>. В сумме все хорошо!
}}
== Немного псевдокода ==
<code>
struct PST
point root
point min_y, max_y
PST *down, *up
// pts sorted by y
PST * build_PST(vector<point> pts)
if (pts.size() == 0)
return NULL
min_y = max_ y = root = min_element(pts) // by x
remove_element(pts, root)
int mid = pts.size() / 2
vector<point> down_pts = pts[0..mid]
vector<point> up_pts = pts[mid+1..pts.size() - 1]
down = build_PST(down_pts)
up = build_PST(up_pts)
if (down != NULL)
min_y = min(min_y, down->min_y)
if (up != NULL)
max_y = max(max_y, up->max_y)
void req(PST * tree, int y1, int y2, int x_max, vector<point> & ans)
if (tree == NULL)
return
if (x_max < tree->root.x)
return
if (y1 > tree->max_y || y2 < tree->min_y)
return
if (tree->root in [y1..y2]x[-inf;x_max])
answer.push_back(tree->root)
req(tree->down, y1, y2, x_max, ans)
req(tree->up, y1, y2, x_max, ans)
</code>
Priority Search Tree позволяет решать следующую задачу. Даны <tex>n</tex> точек, а также запросы. Каждый запрос характеризуется отрезком по одной координате <tex>[y_1, y_2]</tex>, а также числом <tex>x_q</tex> по другой координате. Для каждого запроса структура возвращает все точки, которые находятся в отрезке <tex>[y_1, y_2]</tex> по одной координате, и имеют другую координату не больше <tex>x_q</tex>. На каждый запрос дерево отвечает за <tex>O(\log\,n + k)</tex>, где <tex>k</tex> {{---}} количество точек в ответе.
== Как строится? ==
Дерево строится рекурсивно. Выберем точку с наименьшей <tex>x</tex>-координатой (если таких несколько, то из них выберем с наименьшим <tex>y</tex>). Все остальные точки отсортируем по <tex>y</tex> и разобьем на две равные (количество может отличаться на один) части. Далее будем считать, что все точки первой части имеют координату <tex>y</tex> меньше всех точек второй части (с одинаковыми <tex>y</tex> поступаем как обычно {{---}} сравниваем по <tex>x</tex>). Для каждого из двух множеств, если оно не пусто, построим дерево рекурсивно.
{{Теорема
|statement=
PST занимает <tex>O(n)</tex> памяти.
|proof=
Каждая точка будет корнем ровно одного дерева. Количество деревьев не превышает количества точек. В сумме <tex>O(n)</tex>.
}}
{{Теорема
|statement=
Максимальная глубина PST <tex>O(\log\,n)</tex>.
|proof=
При рекурсивном вызове количество точек уменьшается как минимум в два раза.
}}
{{Теорема
|statement=
Построение PST работает за <tex>O(n\log\,n)</tex> времени.
|proof=
Необходимо отсортировать точки по <tex>y</tex> {{---}} для этого необходимо <tex>O(n\log\,n)</tex>. Построение каждого дерева требует <tex>O(k)</tex>, где <tex>k</tex> {{---}} количество точек в дереве, чтобы найти минимальную по <tex>x</tex> точку, а также для построения новых списков точек для сыновей. На каждом уровне <tex>O(n)</tex> точек, уровней <tex>O(\log\,n)</tex>, значит, в сумме тоже <tex>O(n\log\,n)</tex>.
}}
== Как отвечать на запрос? ==
Если <tex>x</tex> корня больше <tex>x_q</tex>, то никакие точки дерева не могут быть в ответе. Будем хранить также минимальную и максимальную по <tex>y</tex> точки, которые лежат в поддереве. Тогда, если отрезок запроса по <tex>y</tex> не пересекается с отрезком по <tex>y</tex> всех точек поддерева, то также никакие точки из дерева не должны быть добавлены в ответ. Если корень дерева лежит в нужном интервале, добавим его в ответ. Вызовем рекурсивно поиск ответа для двух сыновей.
{{Теорема
|statement=
Будет получен правильный ответ на запрос.
|proof=
Вроде бы очевидно.
}}
{{Теорема
|statement=
Ответ на запрос работает за <tex>O(\log\,n+k)</tex>, где <tex>k</tex> {{---}} размер ответа.
|proof=
Тут все сложнее. Представим, что мы ищем <tex>y_1</tex> и <tex>y_2</tex> (из запроса) в PST как в обычном дереве поиска по <tex>y</tex>. Рассмотрим все точки, которые лежат между двумя путями поиска. Среди них рассмотрим точки с <tex>x <= x_q</tex>. Ровно эти точки и есть ответ. Разобьем все вершины на три группы. Первая {{---}} вершины, которые лежат хотя бы на одном из двух путей. Их <tex>O(\log\,n)</tex>. Вторая {{---}} вершины, которые находятся между двумя путями. Третья {{---}} все остальные. Время обработки вершин первой группы не превышает <tex>O(\log\,n)</tex>. Как только мы зашли в вершину третей группы, сразу поймем, что отрезок по <tex>y</tex> не пересекается с запросом и выйдем. А зайти в них мы можем только из вершин, которые лежат на двух путях (а их <tex>O(\log\,n)</tex>). Отлично! Зайдя в вершину второй группы, мы либо ее добавим в ответ и продолжим, либо выйдем, так как единственная причина, почему корень не подошел {{---}} его <tex>x</tex> слишком большой, а, значит, и все вершины поддерева не подходят. В итоге их обработка занимает <tex>O(k)</tex>. В сумме все хорошо!
}}
== Немного псевдокода ==
<code>
struct PST
point root
point min_y, max_y
PST *down, *up
// pts sorted by y
PST * build_PST(vector<point> pts)
if (pts.size() == 0)
return NULL
min_y = max_ y = root = min_element(pts) // by x
remove_element(pts, root)
int mid = pts.size() / 2
vector<point> down_pts = pts[0..mid]
vector<point> up_pts = pts[mid+1..pts.size() - 1]
down = build_PST(down_pts)
up = build_PST(up_pts)
if (down != NULL)
min_y = min(min_y, down->min_y)
if (up != NULL)
max_y = max(max_y, up->max_y)
void req(PST * tree, int y1, int y2, int x_max, vector<point> & ans)
if (tree == NULL)
return
if (x_max < tree->root.x)
return
if (y1 > tree->max_y || y2 < tree->min_y)
return
if (tree->root in [y1..y2]x[-inf;x_max])
answer.push_back(tree->root)
req(tree->down, y1, y2, x_max, ans)
req(tree->up, y1, y2, x_max, ans)
</code>
