Изменения

<tex>Pr_0 \leq q = 1 - p^{(j + 1)}</tex>, потому что это в сущности вероятность того, что ни одна точка из как минимум <tex>j + 1</tex> непустых четвертинок не попала на уровень выше.

<tex>Pr_1 Pr_0 \leq q^{(j + 1) }</tex>, потому что это в сущности вероятность того, что ни одна точка из как минимум <tex>j + 1</tex> непустых четвертинок не попала на уровень выше. <tex>Pr_1 \cdot p^{leq (j + 1)}\cdot pq^j</tex>, потому что это в сущности вероятность того, что ровно одна точка из как минимум <tex>j + 1</tex> непустых четвертинок попала на уровень выше.

<tex>E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (pq^{(j + 1)} + (j + 1) \cdot ppq^{(j + 1)}) \leq \sum\limits_{j = 1}^{\infty} j \cdot (pq^{(j + 1)} + (j + 1) \cdot ppq^{(j + 1)})</tex>

Это почти геометрическая прогрессия, только на полином домножили, определяется всё равно экспоненциальным множителем, так что это <tex>O(1)</tex>. Можно совсем строго оценить, но и так понятно, что ряд сходится, а сойтись он может только к константе.

Как и [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | range tree]], данная структура умеет выдавать точки, принадлежащие какому-то прямоугольнику, алгоритм очень похож на тот, который применяется в range tree. Только ответ на запрос происходит за <tex>O(\log n+ k)</tex> (вроде бы независимо от размерности, хотя квадродерево подразумевает двумерное пространство, но для обобщения на больше размерности асимптотика будет та же, кажется). И памяти нужно <tex>O(n)</tex>. Этим skip quadtree круче.