我给出了一个反射(reflect)我的用例的示例:
我有一个直方图，范围为 [0, 10000]。我想有效地支持以下类型的查询:
int j = maxYInXRange(20, 70);
应返回给定 X 范围内的最大 Y 值。
我遇到过一种在计算机图形学中使用的称为“优先级搜索树”的数据结构，但没有关于此主题的易于理解的资源。
最佳答案
我相信您正在尝试解决 range minimum/maximum query problem 。如果您在开始时花费更多时间预先计算信息，则可以通过多种方法实现每次查询的亚线性时间。有一个关于几种有效方法的很好的教程 here .
例如，如果您的直方图没有改变，您可以使用 O(1) 的稀疏表回答查询，并使用 O(N log N) 时间和内存进行预计算，其中 N 是表中的元素数量直方图。如果你的直方图经常变化，可以使用线段树进行 O(log N) 更新和查询，一开始就用 O(N) 时间和内存进行一次性预计算。
关于java - 范围内最大/最小值的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32760149/