问题描述
给定一个n个元素的序列{A1，A2，……，，An}，在要求的区间Query（L,R）内找到最小值：min{AL,AL+1,……,AR}。hiho16
算法描述
在这里介绍最常用的Tarjan的Sparse-Table算法，它的预处理时间复杂度为O(nlogn)，而查询时间只需要O(1)。令calc(i,j)表示从i开始的，长度为2j 的一段子序列的最小值，则使用循环的方式计算：calc[i][j] = min(calc[i][j-1],calc[i+2j-1)][j-1])，代码如下：
void RMQ_init(void){int index = floor(log(n) / log(2));for (int j = 1; j <= index; j++) {for (int i = 1; i+(1<<j)-1<=n; i++){calc[i][j] = min(calc[i][j-1],calc[i+(1<<(j-1))][j-1]);}}}
注：这里序列从索引1开始。 预处理完成后，如何使用该信息呢，对于一个查询[L,R]，只要找到小于这个区间长度的最大的2的非负整数次幂的指数——j，那么这个区间中的最小值就是min{calc[L][j], calc[R-2j+1][j]}，通过这两段区间可以覆盖整个[L,R]区间，同时即使两端区间有交集也不影响最小值的确定。
代码;int arr[SIZE];int calc[SIZE][20];int n, q;void RMQ_init(void){int index = floor(log(n) / log(2));for (int j = 1; j <= index; j++) {for (int i = 1; i+(1<<j)-1<=n; i++){calc[i][j] = min(calc[i][j-1],calc[i+(1<<(j-1))][j-1]);}}}int main(void) {scanf(“%d”, &n);for (int i = 1; i <= n; i++){scanf(“%d”, arr + i);calc[i][0] = arr[i];}RMQ_init();scanf(“%d”, &q);int l, r;for (int i = 0; i < q; i++){scanf(“%d%d”, &l, &r);int j = floor(log(r – l + 1) / log(2));int rr = r – (1<<j) + 1;printf(“%d\n”, min(calc[l][j], calc[rr][j]));}return 0;}
灿烂甜美!那一瞬的激-情绽放,催人奋进!胜利,永远属于为梦想奋斗的人新乐吧
