现在给你一个问题：给你一个数组 ，其中有N个数字，现在给你一次询问，给你区间[l ，r]，问你在这个区间内的最大值为多少?
哇！这题简单啊，一个for循环，遍历数组记录最大值输出即可啊。
那好，现在我告诉你假设N为50000，给你Q次询问（(1 ≤ Q ≤ 200,000)）,如果这种情况，我们还每次都进行暴力遍历求解的话，这时算法耗时就会很长。
?
是的，这种暴力遍历求解虽然思维简单，代码简短，但是很慢啊。
那该怎么做呢？这时候就需要RMQ算法来解决这个问题
?
RMQ
（Range Minimum/Maximum Query），
即区间最值查询
。RMQ算法一般用较长时间做预处理，时间复杂度为O(nlogn)，然后可以在O（1）的时间内处理每次查询。
下面我们从一个实际问题来解释RMQ
我们假设数组arr为：1，2，6，8，4，3，7
我们设二维数组dp[i][j]表示从第i位开始连续 个数中的最小值。例如dp[2][1]就表示从第二位数开始连续两个数的最小值（也就是从第二位数到第三位数的最小值），即2，6中的最小值，所以dp[2][1] = 2;
其实我们求 dp[i][j] 的时候可以把它分成两部分，第一部分是从 到 ，第二部分从到 ，为什么可以这么分呢？其实我们都知道二进制数前一个数是后一个的两倍，那么可以把 到 这个区间通过分成相等的两部分，?那么转移方程很容易就写出来了。（
dp[i][0]就表示第i个数字本身）
?
dp[i][j] = min(dp [i][j – 1], dp [i + (1
还没有评论，来说两句吧...