我已经将梅森·布莱恩特的技术修改为有效的方法。问题是 FindLowestIndex 中存在更多错误，并且搜索树时存在更多主要错误（它可以返回多个结果）。
尽管做了这些工作，但仍然没有真正解决问题。 O(n log n)时间设置很容易，但是使用这种技术我只能获取O((log n)^2)查询时间。我想知道您是否有原始问题的链接，以防有更多说明？或者我想知道这个问题是否真的可以解决。或者也许是问题所要求的O((log n)^2)“大约” ，但总比无论如何要少。O(log n)O(n)
该技术是将我们的数组存储在典型的线段树中，但是除了通常的线段信息之外，我们还按顺序存储每个节点下元素的所有索引。O(n log n)如果你正确地添加它（n个项目存储在每个log n级别），这个额外的存储只需要额外的时间/空间，所以它不会以任何重要的方式影响我们的设置时间。然后我们查询树以找到 (a, b) 范围内包含的最小节点集。此查询与典型的线段树查询 ( ) 花费的时间大约相同O(log n)，并且最多找到大约 2*log n 个匹配线段。当我们查询时，我们找到每个匹配段中与我们的约束 c 匹配的最低索引。我们可以使用二分搜索来查找该索引，因为我们保持索引有序，因此O(log n)每个匹配节点在最坏情况下都需要时间。当我们适当地把它们全部加起来时，总时间是O((log n)^2)。
请告诉我您想要澄清的任何步骤。
C# 代码：
void Test() {
DateTime start;
TimeSpan at = new TimeSpan(), bt = new TimeSpan();
Random rg = new Random();
for(int i = 0; i < 20; i++) {
// build arrays from 5 to 10000 elements long, random values between 0 and 100
// Break even time for queries is around 10000 elements in array for the values and queries used
int[] array = (from n in Enumerable.Range(1, rg.Next(5, 10000)) select rg.Next(0, 100)).ToArray<int>();
// Setup should be O(n log n) time/space
ArraySearcher Searcher = new ArraySearcher(array);
// Test each array a number of times equal to its length, with random values for a, b, c
for(int j = 0; j < array.Length; j++) {
int a = rg.Next(-1, 101), b = rg.Next(a, 102), c = rg.Next(0, array.Length);
start = DateTime.Now;
int expected = BruteSearch(array, a, b, c);
at += DateTime.Now - start;
// Search should be O(log n) time, but in reality is O((log n)^2) :(
start = DateTime.Now;
int got = Searcher.QuickSearch(a, b, c);
bt += DateTime.Now - start;
System.Diagnostics.Debug.Assert(got == expected);
}
}
MessageBox.Show(at.ToString() + ", " + bt.ToString());
}
int BruteSearch(int[] array, int a, int b, int c) {
for(int i = c; i < array.Length; i++)
if(a < array[i] && array[i] < b)
return i;
return -1;
}
class ArraySearcher {
SegmentNode Root;
List<SegmentNode> Nodes;
public ArraySearcher(int[] array) {
Nodes = array.Select((value, index) => new SegmentNode(value, value, new List<int> { index }, null, null)).ToList<SegmentNode>();
// Sorting will take us O(n log n)
Nodes.Sort();
// Creating a normal segment tree takes O(n log n)
// In addition, in this tree each node stores all the indices below it in order
// There are a total of n of these indices at each tree level, kept in order as we go at no extra time cost
// There are log n levels to the tree
// So O(n log n) extra time and space is spent making our lists, which doesn't hurt our big O notation compared to just sorting
this.Root = SegmentNode.Merge(Nodes, 0, Nodes.Count - 1);
}
public int QuickSearch(int a, int b, int c) {
return this.Root.FindLowestIndex(a, b, c);
}
class SegmentNode : IComparable {
public int Min, Max;
public List<int> Indices;
public SegmentNode Left, Right;
public SegmentNode(int Min, int Max, List<int> Indices, SegmentNode Left, SegmentNode Right) {
this.Min = Min;
this.Max = Max;
this.Indices = Indices;
this.Left = Left;
this.Right = Right;
}
int IComparable.CompareTo(object other) {
return this.Min - ((SegmentNode)other).Min;
}
public static SegmentNode Merge(List<SegmentNode> Nodes, int Start, int End) {
int Count = End - Start;
if(Start == End)
return Nodes[Start];
if(End - Start == 1)
return SegmentNode.Merge(Nodes[Start], Nodes[End]);
return SegmentNode.Merge(SegmentNode.Merge(Nodes, Start, Start + Count/2), SegmentNode.Merge(Nodes, Start + Count/2 + 1, End));
}
public static SegmentNode Merge(SegmentNode Left, SegmentNode Right) {
int LeftCounter = 0, RightCounter = 0;
List<int> NewIndices = new List<int>();
while(LeftCounter < Left.Indices.Count || RightCounter < Right.Indices.Count) {
if(LeftCounter < Left.Indices.Count && (RightCounter == Right.Indices.Count || Left.Indices[LeftCounter] < Right.Indices[RightCounter]))
NewIndices.Add(Left.Indices[LeftCounter++]);
else
NewIndices.Add(Right.Indices[RightCounter++]);
}
return new SegmentNode(Left.Min, Right.Max, NewIndices, Left, Right);
}
public int FindLowestIndex(int SeekMin, int SeekMax, int c) {
// This will find at most O(log n) matching segments, always less than 2 from each level of the tree
// Each matching segment is binary searched in at worst O(log n) time
// Total does indeed add up to O((log n)^2) if you do it right
if(SeekMin < this.Min && SeekMax > this.Max)
return FindLowestIndex(this.Indices, c);
if(SeekMax <= this.Min || SeekMin >= this.Max)
return -1;
int LeftMatch = this.Left.FindLowestIndex(SeekMin, SeekMax, c);
int RightMatch = this.Right.FindLowestIndex(SeekMin, SeekMax, c);
if(LeftMatch == -1)
return RightMatch;
if(RightMatch == -1)
return LeftMatch;
return LeftMatch < RightMatch ? LeftMatch : RightMatch;
}
int FindLowestIndex(List<int> Indices, int c) {
int left = 0, right = Indices.Count - 1, mid = left + (right - left) / 2;
while(left <= right) {
if(Indices[mid] == c)
return c;
if(Indices[mid] > c)
right = mid - 1;
else
left = mid + 1;
mid = left + (right - left) / 2;
}
if(mid >= Indices.Count)
return -1;
// no exact match, so return the next highest.
return Indices[mid];
}
}
}