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