基于ST表的RMQ算法

基于ST表的RMQ算法可以在O(1)的时间复杂度内计算出一个区间内的最值。

基本思想是将一段长度中的最值保存下来。查询的时候直接返回。避免了常规算法中的一次一次比较的操作。

详细请参考书籍：《算法竞赛入门经典训练指南》–刘汝佳

这里仅谈论我自己的理解。

---

对于长度为n的数组，我们可以知道其二叉树深度不会超过log2 n。

此时就可以创建一个二维数组d[n][logn]。

d[i][j]代表以i为起点，长度为2^j区间上的最值。

在输入进数组之后，首先将d[i][0]赋值为a[i],

然后使用循环，计算出以i为起点，不同长度区间上的值

for(int j = 1; n-(1 << j) >= 0; j++) {
 // warning! this is j !

 for(int i = 1; i <= (n - (1 << j)); i++) {
  //从0-(n - (1 << j))为起点才有相应的长度，n - (1 << j)之后为起点到末尾的长度就不够了。

  d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
  // d[i][j]存储的是以i为起点，长度为2^j的区间内的最大值

 }
}

以上就是预处理操作。

而查询[l,r)区间内的最大值的操作为

int query(int l, int r) {

 int x = 0;

 while(l + (1 << x) < r + 1) { // find the max of x which 2^x <= length;

  x++;

 }

 return max(d[l][x], d[r - (1 << x) + 1][x]); // warning ! this must  is r-(1<<x)+1 !

}