【模板】Sparse-Table

　　范围最小值问题(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 }

[C++]

　　查询操作也很简单，令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 }

[C++]