Skip quadtree: определение, время работы

Конспект готов к прочтению.

Описание

По картинке должно быть понятно

Skip quadtree — как skip list, только вместо list'а quadtree. Поэтому желательно знать, что такое skip list, и необходимо знать, что такое сжатое квадродерево. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажется.

The randomized skip quadtree — последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества [math]S[/math]. [math]S_0 = S[/math], в [math]S_1[/math] каждый элемент из [math]S_0[/math] входит с вероятностью [math]p \in (0, 1)[/math] и так далее. The randomized skip quadtree состоит из последовательности [math]\{Q_i\}[/math], где [math]Q_i[/math] — сжатое квадродерево над множеством [math]S_i[/math]. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из [math]S[/math]. Заметим, что если какой-то квадрат интересный в [math]Q_i[/math], то он интересный и в [math]Q_{i-1}[/math].

Операции над skip quadtree

Будем для каждого интересного квадрата на каждом уровне хранить указатели на тот же квадрат уровнем ниже и уровнем выше (если есть).

Локализация выполняется аналогично сжатому квадродереву. Под локализацией подразумевается, что мы хотим найти минимальный интересный квадрат, содержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далее, пока не дойдём до дна.

Для добавления сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в нулевой уровень, затем с вероятностью [math]p[/math] добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно увеличиться максимум на 1, то есть, если появился новый уровень, то процесс точно заканчивается. Хотя не, давайте без последнего условия, вроде с ним только лучше, но без него проще доказывать.

Удаление совсем просто: локализуемся, удаляем со всех уровней, на которых есть. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.

Время работы и память

Лемма (О количестве шагов на одном уровне):

На каждом уровне в среднем совершается [math]O(1)[/math] шагов поиска для любой точки [math]x[/math].

Доказательство:

[math]\triangleright[/math]

Пусть в [math]Q_i[/math] (то есть на [math]i[/math]-ом уровне) поиск точки [math]x[/math], начинающийся с корня, проходит по квадратам [math]p_0, p_1, \dots, p_m[/math]. Пусть случайная величина [math]j[/math] — количество шагов поиска в [math]Q_i[/math], тогда [math]p_{m - j}[/math] — последний квадрат из [math]p_0, p_1, \dots, p_m[/math], являющийся интересным в [math]Q_{i + 1}[/math]. Оценим вероятность того, что делается [math]j[/math] шагов. Забьём на случай [math]j = 0[/math], так как он не важен при расчёте мат. ожидания. На пути [math]p_{m - j + 1} \dots, p_m[/math] будет хотя бы [math]j + 1[/math] непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустые четвертинки, одна из них — следующий квадрат на пути, в котором тоже хотя бы 2 непустые четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустые четвертинки. Чтобы [math]p_{m - j}[/math] был последним из [math]p_0, p_1, \dots, p_m[/math] интересным квадратом в [math]Q_{i + 1}[/math] небходимо, чтобы среди этих как минимум [math]j + 1[/math] непустых четвертинок только одна (вероятность этого назовём [math]Pr_1[/math]) или ноль (вероятность этого назовём [math]Pr_0[/math]) были непустыми в [math]Q_{i + 1}[/math]. Иначе, если будет хотя бы пара непустых четвертинок, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже [math]p_{m - j}[/math]. Таким образом, искомая вероятность не превосходит [math]Pr_0 + Pr_1[/math]. Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет. Хотя я постарался расписать поподробней, чем в статье. [math]q = 1 - p[/math] [math]Pr_0 \leq q^{(j + 1)}[/math], потому что это в сущности вероятность того, что ни одна точка из как минимум [math]j + 1[/math] непустых четвертинок не попала на уровень выше. [math]Pr_1 \leq (j + 1) \cdot pq^j[/math], потому что это в сущности вероятность того, что ровно одна точка из как минимум [math]j + 1[/math] непустых четвертинок попала на уровень выше. В общем, если чуть подумать, оценки на [math]Pr_0[/math] и [math]Pr_1[/math] довольно ясны. [math]E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (q^{(j + 1)} + (j + 1) \cdot pq^j) \leq \sum\limits_{j = 1}^{\infty} j \cdot (q^{(j + 1)} + (j + 1) \cdot pq^j)[/math] Это почти геометрическая прогрессия, только на полином домножили, определяется всё экспоненциальным множителем, так что это [math]O(1)[/math]. Можно совсем строго оценить, но и так понятно, что ряд сходится, а сойтись он может только к константе.

[math]\triangleleft[/math]

Лемма (О количестве уровней):

Математическое ожидание количества уровней составляет [math]O(\log(n))[/math]

Доказательство:

[math]\triangleright[/math]

Для оценки мат. ожидания посчитаем вероятность того, что количество уровней [math]h[/math] равно [math]k[/math]. [math]p(h = k) = p(h \leq k) \cdot p(h \geq k)[/math]. [math]p(h \leq k) = (1 - p^{k + 1})^n[/math], потому что вероятность того, что точка дойдёт до уровня [math]k + 1[/math], равна [math]p^{k + 1}[/math]. [math]p(h \geq k) = (1 - (1 - p^k)^n)[/math], потому что вероятность того, что точка не дойдёт до уровня [math]k[/math], равна [math]1 - p^k[/math]. А вот нифига не так, я тут понял. Там зависимые события, поэтому перемножать вероятности так нельзя, но всё не сильно портится. [math]p(h = k) = 1 - p(h \gt k) - p(h \lt k) = 1 - (1 - (1 - p^{k + 1})^n) - (1 - p^{k})^n = (1 - p^{k + 1})^n - (1 - p^k)^n \leq np^k[/math], и дальше этой оценки достаточно. [math]E(h) = \sum\limits_{k = 1}^{\infty} k \cdot p(h = k) = p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n + \sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k)[/math] Оценим первую сумму: [math]p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n \leq p(1) \cdot \log_{1/p} n + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n = O(\log(n))[/math], поскольку сумма этих вероятностей не превосходит единицу. Оценим вторую сумму: [math]\sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k) = \leq \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot n p^k = n \cdot \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k[/math] Рассмотрим эту сумму: [math]\sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k = p^{\log_{1/p} n} \cdot \sum\limits_{k = 0}^{\infty} (k + \log_{1/p} n) \cdot p^k = p^{\log_{1/p} n} \cdot (\sum\limits_{k = 0}^{\infty} (k p^k) + \log_{1/p} n \cdot \sum\limits_{k = 0}^{\infty} (p^k)) = p^{\log_{1/p} n} \cdot (O(1) + \log_{1/p} n \cdot O(1)) = 1/n \cdot O(\log(n))[/math] Суммируя всё вышесказанное, получаем, что [math]O(\log(n))[/math]. Для лучшего понимания можно представлять, что [math]p = 1/2[/math].

[math]\triangleleft[/math]

Теорема (О времени работы):

Поиск, добавление и удаление точки работают за [math]O(\log(n))[/math] в среднем.

Доказательство:

[math]\triangleright[/math]

Достаточно очевидно из предыдущих лемм.

[math]\triangleleft[/math]

Теорема (О занимаемой памяти):

Математическое ожидание занимаемой памяти — [math]O(n)[/math].

Доказательство:

[math]\triangleright[/math]

Сжатое квадродерево для [math]n[/math] точек занимает [math]O(n)[/math] памяти. На нулевом уровне [math]n[/math] точек. На следующем уровне [math]p \cdot n[/math] точек, дальше [math]p^2 \cdot n[/math] и так далее. Получим геометрическую прогрессию, в итоге [math]O(n)[/math] памяти.

[math]\triangleleft[/math]

В чём профит?

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

Как отвечать на запрос

Сначала локализуем все четыре точки прямоугольника

Я тут понял, что пока не знаю, как это делать, сейчас буду думать.

Всё очень плохо, я тупой, меня можно побить.

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

Источник

http://arxiv.org/pdf/cs.cg/0507049.pdf