范围内最大/最小值的数据结构

Question

我给出的例子反映了我的使用情况:

我有一个直方图，在范围[0, 10000]。我想有效地支持以下类型的查询:

int j = maxYInXRange(20, 70);

应返回给定X范围内Y的最大值。

我在计算机图形学中遇到了一种叫做"优先搜索树"的数据结构，但是在这个主题上没有容易理解的资源。

Answer 1

我相信你正在尝试解决范围最小/最大查询问题。如果您在开始时花更多的时间预计算信息，那么有许多方法可以实现每次查询的亚线性时间。这里有一个关于几种有效方法的很好的教程。

例如，如果你的直方图没有改变，你可以用一个稀疏表在O(1)内回答查询，预计算使用O(N log N)时间和内存，其中N是直方图中元素的数量。如果您的直方图经常更改，则可以使用段树进行O(log N)次更新和查询，在开始时使用O(N)时间和内存进行一次性预计算。

Answer 2

使用subMap(K,boolean,K,boolean)方法的标准TreeMap呢?

TreeMap histogram = ...
return histogram.subMap(20,true,70,true).values().stream().max()

查找边界将是O(log n)。找到最大值将是O(m)，其中m = max-min。我不认为你能找到一个更好的数据结构，除非你预先计算一切，这将占用O(n²)在计算和存储大小，我想。

Answer 3

您可以按值对直方图索引进行排序，从高到低。然后，对于给定的范围，像这样迭代它:

List<Entry> histogramEntries = ... //sorted by value

for(Entry entry: histogramEntries)
  if(range.contains(entry.index))
     return entry.value;

对于较大的范围，这将工作得更快，因为它更有可能包含列表开头的较大值之一。