这是DSA 2023 Spring PA 3的Nearest Neighbor的解题报告，内容涉及kd树。这篇文章还说明了九成测最后三个测试点Wrong Answer的一个可能原因，以及五成测仅能通过1个测试点的一个可能原因。
A.所使用数据结构与算法的构思、原理和实现要点
所使用的数据结构：
kd树。
算法构思：
1 输入数据之后，从根节点开始递归建树。
2 建树时，如果不是根节点，则按指定轴排序后，记录中值坐标并向子节点继续递归。如果已经到达根节点，建立节点并返回。
3 建树完成后，逐个查询并输出结果。查询时，如果到达叶子结点，将当前点设为暂时的最近点，获得距离并返回开始解递归；如果没有到达叶子节点，根据坐标向左或右继续递归，递归完成后，检查另一侧是否可能有距离更小的点，如果可能，再向另一侧递归查询。
实现要点：
1 递归建树时，设置所有的建树区间为左闭右开区间，以避免特殊情况判断。
2 tree数组中非叶子节点只记录划分所依据的轴和坐标，叶子结点只记录输入的点坐标信息。
3 为了利用 cstdlib 库的 qsort ，将其进行一些封装，使其可以按指定轴排序。
B.完成过程中遇到的问题，排除问题的主要过程、使用的方法和技巧，以及参考资料
问题1：刚开始提交时，五成测的测试点仅能通过1个。
当时，我建立的树的非叶子节点，也是直接使用输入的点建立的。这样做不符合kd树的常规建构方式，也没法解决递归中的很多问题。最终，我按照kd树节点表示点的集合的思路，构建了正确的kd树，只有叶子节点由单个输入节点直接构成。
问题2：九成测有3个测试点出现 Wrong Answer。
考虑到九成测最后三个数据点数据量一般较大，首先考察的两个可能错因是：1 int 和 long long 转换存在漏洞，单个数据运算结果太大，超出变量范围导致错误。2 数据规模很大，导致超出数组范围，因为触碰到其他数组内容而没有触发 Runtime Error 且出现了错误。
经过构造极端数据测试，排除了可能性1，于是考虑可能性2。当时，表示树的tree数组预留的位置是200000，即2倍于最大输入数据规模。在建立二叉树的过程中，考虑到100000不是2的幂，因此会有只有1个子节点的内部节点出现，这就意味着增加的非叶子节点数目可以超过100000。为了确保安全，将数组大小增加到300000，于是通过了所有测试点。
参考资料
除了习题课PPT，没有参考其他资料。
C.时间和空间复杂度的估算
时间复杂度
kd树单词搜索所消耗的时间是O(n^0.5)。题目中规定，询问个数为q，所以总体复杂度为O((n^0.5)*q)。
空间复杂度
由于使用的是定长结构体数组，所以开辟的空间是常数值。
实际使用的空间大小与节点个数成线性关系O(n)，因为所有n个点的数据都只存储了常数次，而q次查询都是即时处理，根本不存储。