Изменения

{{ptready}}''В списке билетов была опечатка, поэтому возникла путаница во многих местах. В этой статье оставляю просто всё полезное (и не очень) про квадродеревья, потому что нужно для скип-квадродерева.'' 

Вообще говоря, квадродеревья могут быть использованы для разных целей и хранить разные данные, но нам они нужны для перечисления точек в произвольном прямоугольнике, соответственно, мы хранить в них будем какой-то набор точекна плоскости.

Глубина квадродерева для множества точек <tex>P</tex> не превосходит <tex>log\log_2(s / c) + 31/2</tex>, где <tex>c</tex> {{---}} наименьшее расстояние между двумя точками из <tex>P</tex>, а <tex>s</tex> {{---}} сторона квадрата, с которого начинается построение квадродерева.

Сторона квадрата на глубине <tex>i</tex>, очевидно, равна <tex>s / 2^i</tex>. Максимальное расстояние между двумя точками внутри квадрата достигается, когда они являются вершинами диагонали, то есть на глубине <tex>i</tex> расстояние между любыми двумя точками в одном квадрате не превосходит <tex>s \sqrt 2 / 2^i</tex>. Поскольку внутренняя вершина квадродерева содержит хотя бы 2 точки в соответствующем ей квадрате, то <tex>s \sqrt 2 / 2^i \geq c</tex>, так как <tex>c</tex> {{---}} минимальное расстояние между точками в <tex>P</tex>. Отсюда следует, что <tex>i \leq log\log_2(s \sqrt 2 / c) = log \log_2 (s / c) + 1/2</tex>. Значит, глубина любой внутренней вершины не превосходит <tex>log \log_2 (s / c) + 1/2</tex>, из чего следует утверждение леммы (так как самый глубокий лист лежит на 1 глубже самой глубокой внутренней вершины).

Каждая внутренняя вершина содержит хотя бы одну точку в соответствующем ей квадрате. Заметим, что квадраты с одного уровня не пересекаются и полностью покрывают весь исходный квадрат (в котором <tex>n</tex> точек). Значит, число внутренних вершин одного уровня не может первосходить превосходить <tex>n</tex>. Из этого следует, что всего внутренних вершин <tex>O(d \cdot n)</tex>.

При построении квадродерева наиболее длительная операция на каждом шаге {{---}} распределение точек по четвертям текущего квадрата. Таким образом, время, затрачиваемое на одну внутренню внутреннюю вершину, линейно зависит от числа точек в соответствующем ей квадрате. Как отмечалось выше, на одном уровне суммарно во всех внутренних вершинах не больше <tex>n</tex> точек, из чего следует доказываемая оценка.

''ВидимоКороче, в этом месте заканчивается всё тоя не знаю, как это доказать, и мне кажется, что относится к данному билетуэто не так. Если нам подали прямоугольник, далее идут просто полезные факты содержащий все точки, то мы пройдём по всем вершинам, которых <tex>O(d \cdot n)</tex> (сбалансированное упомянуто просто такнаписано в книжке, а сжатое нужно для первого билетаи лучшей оценки, видимо, нет)''. Возможно, я неправильно понимаю, что от нас хотят. Может быть, можно придумать какие-то оптимизации, ибо так совсем печальная оценка на запрос получается. Также могу предположить, что оценку времени можно улучшить, использовав функцию от размера ответа, но опять же не могу придумать/найти, как это сделать.

Тут можно ещё чтоОни нужны для каких-то написатьтам задач, но вроде это нам не нужнонужны, поэтому оставлю только определениеничего писать не буду.

Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа внутренних вершин, каждая из которых является интересным квадратом (Кэп: то есть для числа интересных квадратов это надо доказать). Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше либо равно <tex>n</tex>:

* пусть в квадродереве доказано для квадродерева для <tex>n > - 1</tex> точек. Рассмотрим кореньДобавим новую точку <tex>x</tex>: сначала найдём наименьший интересный квадрат <tex>p(x)</tex>, у него обязательно должно быть хотя бы 2 непустых ребёнкакоторый её содержит. Если хотя бы один из детей является точкой<tex>x</tex> находится в его пустой четверти, то остальные непустые дети являются деревьямипросто добавляем <tex>x</tex> как лист, в которых суммарно не больше изменив число интересных квадратов. Если же четверть <tex>n - 1p(x)</tex> точек (и в каждом их меньше которую необходимо вставить <tex>nx</tex>). Значит, в них суммарно не больше уже содержит точку <tex>n - 1y</tex> интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве не больше или интересный квадрат <tex>nr</tex> интересных квадратов. Если же все непустые дети корня являются интересными квадратами), то мы всё равно можем применить индукционное предположение ко всем детям и получить то же самоедобавить в дерево интересный квадрат, поскольку во всех поддеревьях который будет меньше содержать <tex>nx</tex> точек (ибо их суммарно и <tex>ny</tex> и везде есть хотя бы однав разных четвертях. Таким образом, при добавлении точки мы увеличиваем количество интересных квадратов не более, так как дети непустые)чем на один. Таким образом, квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин. Глубина, очевидно, тоже <tex>O(n)</tex>, поскольку на каждом уровне есть хотя бы одна вершина (Кэпздесь под вершинами имеются в виду узлы в дереве). При этом оценки получше нет (то есть глубина <tex>\Theta(n)</tex>). На картинке в правом дереве можно на место левого нижнего красного кружка поставить опять такое дерево и так делать сколь угодно долго, получим глубину <tex>\Theta(n)</tex>.

Нам дают точку, хотим найти наименьший интересный квадрат, который её содержит(содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Довольно очевидно, как это делать: просто идём вниз по дереву в нужную четверть, начиная с корня. В какой-то момент закончим, найдя наименьший интересный квадрат, который содержит искомую точку. Дальше легко проверить, есть ли такая точка в квадродереве. Работает, очевидно, за высоту, которая линейно зависит от числа точек (см. выше).