基于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 ! }