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

Question

我给出了一个反射(reflect)我的用例的例子:

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

int j = maxYInXRange(20, 70);

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

我在计算机图形学中遇到过一种名为“优先搜索树”的数据结构，但没有关于该主题的易于理解的资源。

Answer 1

我相信您正在尝试解决 range minimum/maximum query problem .如果您在开始时花更多时间预先计算信息，则有很多方法可以实现每次查询的亚线性时间。有一个关于几种有效方法的好教程 here .

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