考虑以下二维锯齿数组
[0,0] [0,1] [0,2]
(1,0) [1]
[2,0] [2,1] [2,2]
假设我想知道在某个范围内的所有元素例如[0,0]-[2,0]，我想要一个所有这些元素的列表，实现这一目标的最佳方法是什么，是否有任何预先存在的算法可以实现这一目标?
我曾尝试在c#中实现此功能，但没有得到比一些for循环更进一步的东西。
下面的例子更好地提供了我想要达到的目标的进一步细节。
使用上面定义的数组，假设起始索引为[0,0]，范围的结束索引为[2,1]我想创建一个方法，返回在这个范围内的所有索引的值。
预期结果将是该方法返回以下索引的存储值。[0,0] [0,1] [0,2] [1,0] [1,1] [2,0] [2,1]
如果二维数组是"排序"的，也就是说，当你从左到右在每个一维数组中y增加，当你从上到下x增加，你可以找到第一个点和最后一个点，你需要使用二进制搜索O(logn)的总时间，然后在O(k)中报告这两个点之间的每个点，其中k是你需要报告的点的数量(注意你的复杂度在每个算法中将是Omega(k))。
如果2D数组没有排序，并且您只想输出A对和B对之间的所有对:
should_print = False
should_stop = False
for i in range(len(2dArray)):
for j in range(len(2dArray[i]))
should_print = (should_print or (2dArray[i][j] == A))
if should_print:
print(2dArray[i][j])
should_stop = (2dArray[i][j] == B)
if should_stop:
break
if should_stop:
break
如果你只有n一般2d点，你希望回答查询"找到我在给定矩形中的所有点"，有2个数据结构可以帮助你-kd trees和range trees。这两种数据结构提供了很好的查询时间，但它们有点复杂。我不知道你现在的水平是多少，但如果你刚刚开始接触DS和算法，这些数据结构可能是多余的。
编辑(关于范围树和kd树):
首先我将解释范围树背后的基本概念。让我们从回答一维点的范围查询开始。这很简单-只需构建一个bst(平衡搜索树)，并使用它可以回答O(logn + k)中的查询，其中k是报告的点数。构建bst需要O(nlogn)的时间，占用O(n)的空间。
现在，让我们尝试采用这个解决方案并使其适用于2D。我们将为这些点的x坐标建立一个best。对于bst中的每个节点t，用sub(t)表示t的子树中的所有点。现在，对于每个节点t，我们将为sub(t)点的y坐标建立一个bst。
现在，给定一个范围，我们将使用第一个bst来查找包含在x范围内的所有子树，并且对于每个子树，我们将找到包含在y范围内的所有点(注意sub(t)的子树对应的bst保存在t节点)。
查询占用O(log^2n)时间。构建DS需要O(nlog^2n)的时间，最后需要O(nlogn)的空间。我让你们证明这些表述。随着工作量的增加，查询时间可以减少到O(logn)，构建时间可以减少到O(nlogn)。你可以在这里阅读:http://www.cs.uu.nl/docs/vakken/ga/2021/slides/slides5b.pdf.
现在谈谈KD树。这个想法是在中间用一条垂直线分割二维空间，然后在中间用一条水平线分割每一边，以此类推。此DS中的查询时间为O(sqrt(n))，构建时间为O(nlogn)，占用空间为O(n)。你可以在这里阅读更多关于DS的内容:http://www.cs.uu.nl/docs/vakken/ga/2021/slides/slides5a.pdf