RMQ问题（S-T算法）

问题：范围最小值问题（Range Minimum Query，RMQ）
即查询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},如图

image.png

void RMQ_init(const vector<int> &A){
    int n = A.size();
    for(int i = 0; i < n; i++) d[i][0] = A[i]; //从定义可以知道d[i][0] = A[i] 
    for(int j = 1; (1<<j)<=n; j++)             //只需要logn次 
        for(int i = 0; i + (1<<j) - 1 < n; i++){ //注意这里是从0开始顺序i++，只要最计算的边界大等于整个的最右边界即可停止循环 
            d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]);//递归 
        } 
}

这里需要注意的是循环层i，j的顺序不可以改变，因为我们是通过计算从i开始的2^j来递推的，即需要先算出1次方，再以每个i的一次方推出二次方，最后k次方（k为最大的j值）；若是反过来，则无法递推下去。

查询的话，只要让查询区间包含所有的数就行，这里有个问题是二分法中的边界问题，比如n正好为17，这时需要多分一个区间，所以我们直接取比较大的，即看起来正好包含了所有的时候多令k++一次以保证结果的正确。

int RMQ(int L, int R){
    int k = 0;
    while((1<<(k+1)) <= R-L+1) k++;
    return min(d[L][k], d[R-(1<<k)+1][k]);
}