我必须对数组执行一系列范围更新，即在范围中添加或减去一些常量。之后，我必须找到最终数组的范围，即 (max-min)。最初的数字是 1 到 n。
我正在使用二进制索引树。每个更新都在日志 N 中。我想知道是否有办法在 O(n) 或更短的时间内找到 RANGE（或最大值和最小值）。按照惯例，它需要 O(n log n)。
问问题
332 次
3 回答
0
您需要对数组元素进行直接索引访问，因为您需要处理它们以进行增量更新。
您还需要维护最小堆和最大堆。
当你更新一个元素时，你还需要更新两个堆中的对应条目。因此，您需要将指针存储到数组中两个堆中的相应元素中。
创建原始堆是 O(n)，任何修改都是 O(lg(N))。
于 2012-08-07T19:47:00.050 回答
0
为什么不对数组进行一次排序？然后从整个数组中添加或减去一个常数仍然给出相同的顺序，就像乘以一个正数一样。也许还有更多的图片。
于 2012-08-07T23:36:18.673 回答
0
这个问题已经有将近 2 年的历史了，因此我不确定这个答案是否会有很大帮助。无论如何...我从来没有使用 BIT 来回答最小或最大查询。这里有范围查询，它一次改变了很多数字。所以最大值和最小值也会更新。据我所知，除了点查询、范围和搜索等之外，我从未见过在查询中使用 BIT。通常，段树为搜索最小值和最大值提供了更好的选择。执行所有更新后，您可以在 O(lg n) 时间内找到这些更新。但是，在更新期间，您必须更新每个节点的最小最大值，这可以使用延迟传播来完成。更新成本为 O(lg n)。总而言之，如果 m lg n < n 对于您的应用程序，您可以使用分段树，尽管空间更大。
于 2014-10-03T19:50:37.307 回答