算法的一个实现方法如下。

其中使用位运算替代2的幂次的计算，加快运算速度。

使用时需要先调用initRMQ()进行初始化，然后再调用RMQ(u,v)进行查询。

1 const int mx = 10000 + 10;  //数组最大长度 2 int n, a[mx]; //数组长度，数组内容 3  4 int st[mx][30]; //DP数组 5 void initRMQ() 6 { 7     for (int i = 0; i < n; i++) st[i][0] = a[i]; 8     for (int j = 1; (1 << j) <= n; j++) //使用位运算加速 9         for (int i = 0; i + (1 << j) - 1 < n; i++)10             st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);11 }12 13 int RMQ(int u, int v)14 {15     int k = (int)(log(v-u+1.0) / log(2.0)); //类型转换优先级高，除法整体要加括号16     return min(st[u][k], st[v-(1<

有时候需要得到最值的下标而不是最值内容

1 const int mx = 10000 + 10;  //数组最大长度 2 int n, a[mx]; //数组长度，数组内容 3  4 int st[mx][30]; //DP数组 5 void initRMQIndex()  6 { 7     for (int i = 0; i < n; i++)        st[i][0] = i; 8     for (int j = 1; (1 << j) <= n; j++) 9         for (int i = 0; i + (1 << j) - 1 < n; i++)10             st[i][j] = a[st[i][j-1]] < a[st[i+(1<<(j-1))][j-1]] ? 11                                     st[i][j-1] : st[i+(1<<(j-1))][j-1];12 }13 14 int RMQIndex(int s, int v) //返回最小值的下标15 {16     int k = int(log(v-s+1.0) / log(2.0));17     return a[st[s][k]] < a[st[v-(1<