RMQ问题之ST算法
RMQ(Range Minimum/Maximum Query)问题，即区间最值问题。
给你n个数，a1 , a2 , a3 , ... ,an，求出区间 [ l , r ]的最大值。
举例：
a={ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 },求出区间[4 ,8]中的最值。（答案：8 )
这个问题最朴素的想法是用一个循环每次比较大小，但是，当数据范围较大时，这个算法十分低效。这时我们往往使用 ST 算法解决这个问题。虽然线段树和树状数组都能解决，但是ST算法更快。ST算法能做到O(1)时间的查询，而且代码实现更容易。
我们定义 f ( i , j ) 表示从i开始，长度为 2j 的一段区间中的最大值。
例如：在数列3，2，4，5，6，8，1，2，9，7中，f ( 1 , 0 )表示从第一个数开始长度为20的区间内的最大值，即f ( 1 , 0 ) = 3 , 同理f ( 1 , 1 )=3 , f ( 1 , 2 ) =5, f ( 1 , 3 ) =8。从这里很容易发现，f ( i , 0 ) 等于原数列第i个数的值。
可以通过预处理的递推计算f ( i , j )：
f ( i , j ) = max { f ( i , j-1 ) , f ( i+(1<<j-1) , j - 1 ) }
这个方程与动态规划的思想十分相似，这几乎是ST算法的核心，但是，这个方程是什么意思呢？我们将区间[ i , j ]分成两部分[ i , i+2j-1 -1 ] 与 [ i+2j-1 , i+2j -1] , 这两个区间的长度都为2j-1，分别求出两个区间最大值，在取较大的那个，就是原区间的最大值。这就是ST算法的动态转移方程。
举例：数列a={ 1 ，4 ， 2 ， 3 }求f ( 1 , 2 ) =max { f( 1 , 1 ) , f ( 3 , 1 ) }=max { 4 , 3 } = 4 ;
注：初始状态 f ( i , 0 ) = a [i] ;
预处理：
1 void Init()//nlogn 2 { 3 log2[1] = 0; 4 for(int i = 2; i <= n; i++) log2[i] = log2[i >> 1] + 1; //打log2表 5 for(int i = 1; i <= n; i++) f[i][0] = a[i]; //建立初始状态 6 for(int j = 1; (1 << j) <= n; j++) 7 { 8 for(int i = 1; i + (1 << j) - 1 <= n; i++) 9 { 10 f[i][j] = max( f[i][j - 1] , f[i + (1 << j - 1)][j - 1] ); //动态转移方程 11 } 12 } 13 }
查询：
查询区间[a , b ]中最大值，查询的方法比较简单，我们只需要找到一个最大整数 k ，使它满足2k<= b - a +1,例如[ 3 , 11 ] 可以分为 [ 3 , 9 ]
这里我们把待查询的区间分成两个小区间，这两个小区间满足两个条件：（1）这两个小区间要能覆盖整个区间（2）为了利用预处理的结果，要求小区间长度相等。注意两个小区间可能重叠（区间重叠不影响结果）
直接返回 max{ f[a][k] , f[b-(1<<k)+1][k] },于是就求出查询区间中的最大值。
代码如下：
1 int Query(int a, int b) 2 { 3 int k = log2[b - a + 1]; 4 return max( f[a][k] , f[b - (1 << k) + 1][k] ); 5 }
主程序：
1 int main() 2 { 3 int m, u, v; 4 cin >> n; 5 for(int i = 1; i <= n; i++) 6 { 7 cin >> arr[i]; 8 } 9 Init(); 10 cin >> m; 11 while(m --) 12 { 13 cin >> u >> v; 14 if(u > v) swap(u, v); 15 cout << Query(u, v) << endl; 16 } 17 return 0; 18 }
综上，ST算法在只有查询的情况下，十分高效，在做了O(nlogn)的预处理后，可以做到O(1)的时间查询。
2016-09-14
(完)