algorithm - 找到子数组的最大值

Question

在 O(n log n) 时间内对数组 A 进行预处理，以便您可以回答 findmax(i,j) 形式的查询：找到区间 [i; 中的最大值；j]（即数组元素 A[i],A[i + 1],...,A[j]）中的最大值 O(1)）每次查询的时间。

附加问题：展示如何在 O(n) 时间内进行预处理，以便您可以在 O(log n) 时间内回答上述查询。

Answer 1

该问题被称为范围最小（最大）查询 - RMQ。该链接基本上回答了您的两个问题。

经典的解决方案是动态规划和分段树。