范围最小值问题(Range Minimum Query,RMQ)。给出一个长度为n的数组A1,A2,…,An，设计一个数据结构，支持查询操作Query(L,R)：计算min{AL,AL+1,…,AR}
对于这种数组中元素不会进行更新的情形，最常用的是Tarjan的Sparse-Table算法，它用O(nlogn)的时间进行预处理，之后每次查询只要O(1)的时间，而且常数很小
设d[i][j]表示从 i 开始，长度为2^j的一段元素中的最小值，则可以得到递推关系：d[i][j] = min { d[i][j-1] , d[i+2^(j-1)][j-1] }
预处理代码如下：
1 #include<algorithm> 2 #define MAX 100000 3 4 int n; 5 int d[MAX][50]; 6 int A[MAX]; 7 8 void RMQ_init() 9 { 10 for(int i=1;i<=n;i++) 11 d[i][0]=A[i]; 12 for(int j=1;(1<<j)<=n;j++) 13 for(int i=1;i+j-1<=n;i++) 14 d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]); 15 }
查询操作也很简单，令k为满足2^k<=R-L+1的最大整数，则以L开头长为2^k的区间和以R结尾长为2^k的区间合起来刚好覆盖了查询区间[L,R]，由于是取最小值，有些元素重复考虑也没关系
查询代码如下：
1 #include<algorithm> 2 #define MAX 100000 3 4 int n; 5 int d[MAX][50]; 6 int A[MAX]; 7 8 int RMQ(int L,int R) 9 { 10 int k=0; 11 while((1<<(k+1))<=R-L+1) 12 k++; 13 return min(d[L][k],d[R-(1<<k)+1][k]); 14 }