多维段树 [英] Multi-dimensional segment trees

问题描述

我必须解决的问题是第一维问题的四维版本刺杀查询：查找号码所属的间隔。我正在寻找一个多维执行分段树。理想情况下，它将使用Java，它将使用小数级联。

The problem I have to solve is the 4D version of the 1D problem of stabbing queries: find which intervals a number belongs to. I am looking for a multi-dimensional implementation of segment trees. Ideally, it will be in Java and it will use fractional cascading.

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

Multi-dimensional implementations exist for kd-trees (k-NN searches) and range trees (given a bounding box, find all points in it) but for segment trees I've only found 1D implementations.

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

I'd be happy to consider other data structures with similar space/time complexity to address the same problem.

推荐答案

为了扩展我的评论，我想到的二进制空间分割算法是这样的。

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

1. 选择坐标x和阈值t（随机坐标，中间坐标等）。


2. 分配一个新节点并分配所有间隔与半平面x = t相交。


3. 递归地构造子节点，用于（a）完全在下半空间x t内。

刺根查询从根开始，检查所有间隔s分配给当前节点，下降到适当的子节点，并重复。对于小型子树，可能需要切换到暴力。

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.

如果太多的间隔被半平面x = t刺伤，您可以尝试在（a）与下半空间相交的间隔和（b）与上半空间相交的间隔。这与间隔重复，因此空间要求不再是线性的，您可能必须在间隔集合上切换到暴力，细分证明是无效的。

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.

这篇关于多维段树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！