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

Question

我举了一个反映我的用例的例子：

我有一个直方图，范围是[0, 10000]。我希望高效地支持以下类型的查询：

int j = maxYInXRange(20, 70);

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

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

Answer 1

您可以按值对直方图索引进行排序，从高到低。然后，对于给定的范围，迭代如下：

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


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

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

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

我相信你在试图解决这个问题。如果在开始时花更多的时间预计算信息，有很多方法可以实现每次查询的次线性时间。关于几种有效的方法有一个很好的教程here

例如，如果柱状图没有改变，可以使用O（1）中的稀疏表回答查询，使用O（N logn）时间和内存进行预计算，其中N是柱状图中的元素数。如果柱状图经常更改，则可以使用段树进行O（logn）更新和查询，并在开始时使用O（N）时间和内存进行一次性预计算