Изменения

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

Реализовывать построение можно рекурсивно с помощью функции <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>. Кажется, так и есть, но это не особо надо, просто пусть будет, полезно же.