170
правок
Изменения
Нет описания правки
Оценим вероятность того, что делается <tex>j</tex> шагов. Забьём на случай <tex>j = 0</tex>, так как он не важен при расчёте мат. ожидания. На пути <tex>p_{m - j + 1} \dots, p_m</tex> будет хотя бы <tex>j + 1</tex> непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустые четвертинки, одна из них {{---}} следующий квадрат на пути, в котором тоже хотя бы 2 непустые четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустые четвертинки. Чтобы
<tex>p_{m - j}</tex> был последним из <tex>p_0, p_1, \dots, p_m</tex> интересным квадратом в <tex>Q_{i + 1}</tex> небходимо, чтобы среди этих как минимум <tex>j + 1</tex> непустых четвертинок только одна (вероятность этого назовём <tex>Pr_1</tex>) или ноль (вероятность этого назовём <tex>Pr_0</tex>) были непустыми в <tex>Q_{i + 1}</tex>. Иначе, если будет хотя бы пара непустых четвертинок, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже <tex>p_{m - j}</tex>. Таким образом, искомая вероятность не превосходит <tex>Pr_0 + Pr_1</tex>.
''Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет. Хотя я постарался расписать поподробней, чем в статье.''
Сжатое квадродерево для <tex>n</tex> точек занимает <tex>O(n)</tex> памяти. На нулевом уровне <tex>n</tex> точек. На следующем уровне <tex>p \cdot n</tex> точек, дальше <tex>p^2 \cdot n</tex> и так далее. Получим геометрическую прогрессию, в итоге <tex>O(n)</tex> памяти.
}}
== В чём профит? ==
Как и [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | range tree]], данная структура умеет выдавать точки, принадлежащие какому-то прямоугольнику, алгоритм очень похож на тот, который применяется в range tree. Только ответ на запрос происходит за <tex>O(\log n)</tex> (вроде бы независимо от размерности, хотя квадродерево подразумевает двумерное пространство, но для обобщения на больше размерности асимптотика будет та же, кажется). И памяти нужно <tex>O(n)</tex>. Этим skip quadtree круче.
=== Как отвечать на запрос ===
Сначала локализуем все четыре точки прямоугольника
''Я тут понял, что пока не знаю, как это делать, сейчас буду думать.''
== Источник ==
