我要解决的问题是刺入查询的1D问题的4D版本:找到一个数字属于哪个区间。我正在寻找段树的多维实现。理想情况下，它将在Java中使用分数级联。
多维实现存在于k-树(k-NN搜索)和范围树(给定一个边界框，找到其中的所有点)，但对于段树，我只找到了一维实现。
我很乐意考虑其他具有类似空间/时间复杂性的数据结构来解决相同的问题。
为了详细说明我的评论，我想到的二进制空间分区算法是这样的。
- 选择坐标x和阈值t(随机坐标、中位数坐标等)
- 分配一个新节点，并将与半平面x=t相交的所有间隔分配给它。
- 递归地为(a)完全包含在下半空间x<t内的区间和(b)完全包含在上半空间x>t内的区间构建子节点。
刺入查询从根节点开始，检查分配给当前节点的所有间隔，下降到适当的子节点，然后重复。对于小的子树，切换到暴力破解可能是值得的。
如果太多的区间被半平面x=t所包围，你可以尝试递归(a)与下半空间相交的区间和(b)与上半空间相交的区间。这会重复间隔，因此空间需求不再是线性的，并且您可能不得不切换到对细分证明无效的间隔集合进行蛮力处理。