Изменения

{{ptreadyready}} 

''Примечание: в книжке описывается двумерный вариант, и на лекциях, кажется, только он был, поэтому далее считается, что <tex>k = 2</tex>. Обобщение на большую размерность достаточно просто додумать при необходимости. Местами будет упомянут и случай <tex>k > 2</tex>.'' Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (раз считаембудем считать, что <tex>k = 2</tex>(случай бОльших размерностей обрабатывается аналогично), то поэтому на следующем уровне вновь будем разбивать вертикальными прямыми).

''Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим {{---}} не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате. Не думаю, что об этом нужно много писать.''

Реализовывать построение можно рекурсивно с помощью функции <tex>BuildKdTree(P, Depth)</tex>, принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (в нашем случае при <tex> k = 2 </tex> от чётностиразмерности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:

Умные люди могут сразу же заметить, что решением Решением этого является <tex>T(n) = O(n \log n)</tex>. А люди моего уровня могут почитать умные книжки или просто поверить в данный факт. Хотя могу неформально пояснить: второе слагаемое даёт <tex>O(n)</tex> суммарно, а всего слагаемых из-за неё получится <tex>O(\log n)</tex>. То есть получим <tex>O(n)</tex> из-за второго слагаемого и ещё <tex>O(\log n)</tex> слагаемых вида <tex>O(n)</tex>.

Нетрудно заметитьГлубина дерева рекурсии равна <tex>\log_4 n = \frac{1}{2}\log_2 n</tex>Следовательно, что <tex>Q(n) = O(2^{\frac{1}{2}\log_2 n}) = O(\sqrt n)</tex> является решением. Принимая во внимание всё, что писалось выше, получаем требуемое.

By the way, в общем случае время на запрос <tex>O(n^{1 - 1/k} + ans)</tex>. Быстренько прикинув, я получил соотношение из соотношения <tex>Q(n) = k + 2^{k - 1} \cdot Q(n / 2^k)</tex>. Кажется, так и есть, но это не особо надо, просто пусть будет, полезно же.