<tex>T(n) = O(n) + 2 \cdot T(n / 2)</tex>, otherwise.
Умные люди могут сразу же заметить, что решением этого является <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>O(n)</tex>. Поэтому будет <tex>O(n)</tex> вершин, каждая занимает <tex>O(1)</tex> памяти.
}}
By the way, если считать <tex>k</tex> константой, то и для случая большей размерности эти оценки будут такими же (доказывается аналогично).
== Запрос ==
ЫПусть нам поступил какой-то прямоугольник <tex>R</tex>. Нужно вернуть все точки, которые в нём лежат. Будем это делать рекурсивно, получая на вход корень дерева и сам прямоугольник <tex>R</tex>. Обозначим область, соответствующую вершине <tex>v</tex>, как <tex>region(v)</tex>. Она будет прямоугольником, одна или более границ которого могут быть на бесконечности. <tex>region(v)</tex> можно явно хранить в узлах, записав при построении, или же считать при рекурсивном спуске. Если корень дерева является листом, то просто проверяем одну точку и при необходимости репортим её. Если нет, то смотрим пересекают ли регионы детей прямоугольник <tex>R</tex>. Если да, то запускаемся рекурсивно от такого ребёнка. При этом, если регион полностью содержится в <tex>R</tex>, то можно репортить сразу все точки из него. Тем самым мы, очевидно, вернём все нужные точки и только их. Чтобы стало совсем понятно, приведём псевдокод: <code> SearchKdTree(v, R) //Input. The root of (a subtree of) a kd-tree, and a range R. //Output. All points at leaves below v that lie in the range. if v is a leaf Report the point stored at v if it lies in R. else if region(v.left) is fully contained in R ReportSubtree(v.left) else if region(v.left) intersects R SearchKdTree(v.left, R) if region(v.right) is fully contained in R ReportSubtree(v.right) else if region(v.right) intersects R SearchKdTree(v.right, R) </code> Здесь <tex>ReportSubtree</tex> репортит все точки в поддереве. By the way, точно так же можно перечислять точки в любом множестве, ведь нигде не используется, что <tex>R</tex> {{---}} прямоугольник. {{Теорема|about=О времени на запрос|statement=Перечисление точек в прямоугольнике выполняется за <tex>O(\sqrt n + ans)</tex>, где <tex>ans</tex> {{---}} размер ответа.|proof=Сперва заметим, что все <tex>ReportSubtree</tex> суммарно выполняются за <tex>O(ans)</tex>. Поэтому достаточно доказать оценку для числа рекурсивных вызовов. А рекурсивные вызовы выполняются только для тех вершин, регионы которых пересекают <tex>R</tex>, но не содержатся в нём. Такие регионы обязательно пересекают хотя бы одну (axis-parallel) сторону заданного прямоугольника. Оценим количество регионов, которые могут пересекаться произвольной вертикальной прямой. Для горизонтальной прямой это будет аналогично. Обозначим максимально возможное количество регионов, пересекаемых какой-либо вертикальной прямой, в дереве для <tex>n</tex> точек, у которого первое разбиение делается вертикальной прямой, как <tex>Q(n)</tex>. Рассмотрим произвольную вертикальную прямую <tex>l</tex>. Она будет пересекать регион корня и какого-то одного из его детей (например, левого). При этом ни один из регионов в другом (правом) поддереве пересекать она не может. Левая половина разбита ещё на 2 части горизонтальной прямой, в каждой из них примерно <tex>n / 4</tex> вершин, и они хранятся в поддереве, у которого первое разбиение делается вертикальной прямой. Это даёт нам следующее соотношение: <tex>Q(n) = O(1)</tex> if <tex>n = 1</tex>. <tex>Q(n) = 2 + 2 \cdot Q(n / 4)</tex>, otherwise. Нетрудно заметить, что <tex>Q(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>. Кажется, так и есть, но это не особо надо, просто пусть будет, полезно же.
== Ссылки ==
