1.Range min/max query,即RMQ问题

RMQ问题，指在一个大区间内最值，举个例子：

x[i]:3 5 4 11 5 8 7
query1:求区间[2,4]的最大值
answer1：即max(5,4,11)=11
query2:求区间[3,6]的最小值
answer2: 即min(4,11,5,8)=4

当数据数量较小时，可以选择直接用暴力法用循环求解，但是当数据量较大时，往往时间复杂度过高导致超时，这是我们就要来寻找其他高效的方法了。

解RMQ问题有很多种方法，这里介绍用稀疏表解。

在介绍稀疏表之前，需要了解几个概念与公式：

2.对数

1.对数的概念：如果a^x=b,那么我们定义：log a(b)=x,a叫做底数

2.简单的对数公式：

1. log x (a*b)=log x(a)+ log x(b);
2. 特别重要的换底公式： log a(b)= log c(b)/log c(a);

因为在c++中log的内置函数是ln（后文中所有log都代表ln），因此我们需要通过ln来换底以求对数。

3.前面讲到的ln，指以e(自然对数底，具体值为 lim(n->∞)(1+1/n)^n)为底数的对数，称为自然对数，在高中会着重讲解。

4.根据这些,我们需要预计算打表以2为底的对数，称为log2[N]数组：

for(int i=1;i<=N;i++){
	log2[i]=log2[i/2]+1;
}                      

具体解释为：计算log2[i]用递推，log2[i]=log2[(i/2)*2];根据第一个对数公式，可得log2[i]=log2[(i/2)*2]=log2[i/2]+log2[2];而因为2是2的一次方，所以log2[2]=1;带回式子，可得代码中的递推式。

3.二进制位运算

二进制位运算有两个基本运算：<<(左移）和>>（右移）

1.左移 左移指把一个二进制数向左移动n位，末位补0，即a<<b=a*2^b;

2.右移 右移和左移差不多，移动的方向相反，末位去掉，即a>>b=floor(a/2^b);

4.稀疏图(Sparse Table,简称ST表)

现在开始步入正题了^_^

稀疏图的定义比较巧妙，主要思路就是分块计算RMQ，然后拼拼凑凑~

ST表会选取关键长度，就是所有2的正整数次幂的长度，比如如果一个区间的长度是4，那么他就是个关键长度，如果长度是3，那么不是。

一个