java - 多维线段树

Question

我要解决的问题是 4D 版本的 1D 问题的stabbing 查询：找到一个数字属于哪个区间。我正在寻找分段树的多维实现。理想情况下，它将使用 Java 并使用分数级联。

kd-trees（k-NN 搜索）和范围树（给定一个边界框，找到其中的所有点）存在多维实现，但对于分段树，我只找到了一维实现。

我很乐意考虑其他具有相似空间/时间复杂度的数据结构来解决相同的问题。

Answer 1

To expand on my comment, the binary-space-partitioning algorithm I have in mind is this.

1. Choose a coordinate x and a threshold t (random coordinate, median coordinate, etc.).
2. Allocate a new node and assign all of the intervals that intersect the half-plane x=t to it.
3. Recursively construct child nodes for (a) the intervals contained entirely within the lower half-space x<t and (b) the intervals contained entirely within the upper half-space x>t.

The stabbing query starts at the root, checks all of the intervals assigned to the current node, descends to the appropriate child, and repeats. It may be worthwhile to switch to brute force for small subtrees.

If too many intervals are getting stabbed by the half-plane x=t, you could try recursing on the (a) the intervals that intersect the lower half-space and (b) the intervals that intersect the upper half-space. This duplicates intervals, so the space requirement is no longer linear, and you probably have to switch over to brute force on collections of intervals for which subdivision proves unproductive.