RMQ算法

RMQ: Range Max Query
区间最大值查询。

算法思路

• 使用f[i][j]表示在i到i + 1 << j - 1之间所有数的最大值
• 将第二维降到1 << N的长度，优化了时间复杂度。
• 而在后续查询的过程中，应该找到从l到r之间的最大二次方长度，即满足1 << k < r - l + 1时，k的最大值。 然后将区间分成覆盖的两部分，只要两区间覆盖了要求区间就可以了，不影响答案，所以新的f[l][r]是f[l][k - 1]和f[j - (1 << k - 1) + 1][k-1]的最大值。

Tips:

注意

• 如同区间dp（类似），我们应该以第2维长度作为第一层循环进行枚举。
• j由于表示的是2的指数，因此从0开始。