查找包含单元格的一组区域的algorithm
我正在处理一些电子表格数据，我有一组具有任意边界的单元格区域。 给定任何单元格，确定包含单元格的区域子集的最快方法是什么？
目前，我所能做的最好的是对主要sorting字段作为区域起始行索引，接着是结束行索引，起始列索引，然后结束列索引。 当我想要根据给定的单元格进行search时，我将对二进制search到的第一个区域的起始行索引位于单元格的行索引之后，然后检查所有区域之前是否包含该单元格，但这样太慢。
基于一些谷歌search，这是二维点封闭search问题，或“刺中问题”的一个例子。 看到：
http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf
（从p.21 / 52开始）：
http://www.cs.brown.edu/courses/cs252/misc/slides/orthsearch.pdf
涉及的关键数据结构是分段树：
http://en.wikipedia.org/wiki/Segment_tree
对于二维情况，看起来您可以构build包含分段树的分段树并获得O（log ^ 2（n））查询的复杂性。 （我认为你现在的解决scheme是O（n），因为平均而言，你只需将你的二分之一的区域排除在二进制search之外。）
但是，你说的“电子表格”，这意味着你可能有一个相对较小的区域工作。 更重要的是，你有整数坐标。 而且你说“最快”，这意味着你可能愿意交换空间和设置时间来加快查询速度。
你没有说哪个电子表格，但下面的代码是一个疯狂的低效率，但粗糙的，强大的Excel / VBA实现的二维查找表，一旦build立，具有O（1）查询的复杂性：
Public Sub brutishButShort() Dim posns(1 To 65536, 1 To 256) As Collection Dim regions As Collection Set regions = New Collection Call regions.Add([q42:z99]) Call regions.Add([a1:s100]) Call regions.Add([r45]) Dim rng As Range Dim cell As Range Dim r As Long Dim c As Long For Each rng In regions For Each cell In rng r = cell.Row c = cell.Column If posns(r, c) Is Nothing Then Set posns(r, c) = New Collection End If Call posns(r, c).Add(rng) Next cell Next rng Dim query As Range Set query = [r45] If Not posns(query.Row, query.Column) Is Nothing Then Dim result As Range For Each result In posns(query.Row, query.Column) Debug.Print result.address Next result End If End Sub 如果您有一个更大的网格担心或区域相对于网格较大，则可以使用两个一维查找表来节省大量空间和设置时间。 然而，那么你有两个查找，加上需要采取两个结果集的交集。
我想你想确定单元格和区域的相交是否为空
Sub RegionsContainingCell(rCell As Range, ParamArray vRegions() As Variant) Dim i As Long For i = LBound(vRegions) To UBound(vRegions) If TypeName(vRegions(i)) = "Range" Then If Not Intersect(rCell, vRegions(i)) Is Nothing Then Debug.Print vRegions(i).Address End If End If Next i End Sub Sub test() RegionsContainingCell Range("B50"), Range("A1:Z100"), Range("C2:C10"), Range("B1:B70"), Range("A1:C30") End Sub