查阅了网上的一些资料，目前只找到了 K-D Tree 在进行区域查询（如多维偏序）时的复杂度证明。但是网上存在大量题目是利用 K-D Tree 进行邻域查询（如平面最近点对），但这部分似乎存在争议。OI-Wiki 上认为单查最坏复杂度是 $O(n)$ 的，但也有说法是 $O(\sqrt n)$ 或者均摊每次 $O(\sqrt n)$。

想要请教一下，在进行邻域查询时复杂度到底是怎样的，该如何证明。