c++ - 如何在给定数组的任何子数组(任何大小)中找到最大值(或最小值)？

Question

我们得到了一个数组和一些查询。每个查询包含两个数字i 和j。我们需要在给定数组中从索引 i 到索引 j 的子数组中找到最大(或最小)元素。

例如。

arr = [2 , 3 , 5,  8 , 4 , 9]

和

query 1: (2 , 4)

与此查询对应的子数组将是 [5 , 8 , 4]。因此，最大值将为 8。

注意:查询数量约为10^5，数组中有大约10^6个元素。程序执行的时间限制也是 1s 。因此，我猜想需要一个解决方案，每个查询的复杂度为 O(log n) 或更少，其中 n 是数组中元素的数量。

Answer 1

详细阐述 Yeldar 的 RSQ 想法，并假设您只需要找到最大值(否则，也为最小值重复此结构):- 你已经有了每个条目的值。现在将您的数组分成两对，并存储每对的最大值。 (所以在你的例子中你会得到 3,8,9)。然后将它们分成对(4 个原始条目)并存储其中的最大值(所以 8,9；奇数一个单独保留)。重复直到你下降到一对，给你整个阵列的最大值。因此，您有多个级别的树，每个级别对应一个子数组。

-现在，您可以使用这棵树更有效地找到每个最大值:如果您需要找到从 i 到 j 的最大值，请找到树中完全包含从 i 到 j 的范围的最小子数组。现在你可以看到(从你的树)那个子数组的最大值，所以向下追踪它(因为子数组每个更高级别由两个较低级别的子数组组成)直到你得到完全包含在从 i 到j，或完全不相交。在您跟踪时，请跟踪您未采用的每条路径的最大值。

如果它完全包含在内，您就有了答案(该范围的最大值)。如果它完全不相交，那么它不是你的答案(它来自不在范围内的东西)，所以从你没有走的路径中取最高的最大值并重复这个过程(添加任何新的未采用的路径)，直到你的最大值确实最终来自一个完全包含在该范围内的子数组。