RMQ算法（用于求一个序列任意区间的最大值或者最小值）

参考:https://blog.csdn.net/qq_41311604/article/details/79900893
相当于二分法的逆过程
先获得所有区间大小为2的最值，然后根据这个获得区间大小为4的最值，以此类推
采用的是dp的方法
比如:int arr[15] = { 0,1,3,5,6,4,2,9,7,10,8};(排序的数从1开始，一共10个数)
dp[i][j]:表示从i开始，接下来1<<j(包含i)的最值,arr[1][2] = min(1,3) = 1; arr[2][2] = min(3,5,6,4) = 3
要获得一个开头为i区间大小为1>>j内的最值，可以通过开头为i大小为1>>j-1(前半段)和开头为i+(1>>j-1),大小为1>>j-1(后半段)取得最值得到，例如dp[3][3] = min(dp[3][2],dp[7][2])
转移方程为:
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
总的过程为:
void rmq_init()
{
for (int i = 1; i <= N; i++)
dp[i][0] = arr[i];//初始化
for (int j = 1; (1 << j) <= N; j++)
for (int i = 1; i + (1 << j) - 1 <= N; i++)
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
}
查询部分如果要求一个区间为(i,j)中得最值，区间得大小取对数为k = log(j-i+1)/log(2),所要查询得部分为
min((i,i + 1<<k - 1) , (j - 1 << k + 1, j))
查询得代码为:
int rmq(int i,int j)
{
int k = log(j - i + 1) / log(2);
return min(dp[i][k], dp[j - (1 << k) + 1][k]);
}