RMQ - Region Minimum Query

演算法筆記- Region Minimum Query -
complexity: nlgn

#include<stdio.h>
#include<stdlib.h>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define N 100

//RMQ離線算法 O(N*logN)+O(1)
// INIT: val[]為待查詢數組,  initrmq(n);
int st[20][N], val[N];
int min(int a,int b){return a<b?a:b;}
void initrmq(int n){
    int i, j, k, sk;
    for (i = 0; i < n; i++) st[0][i] = val[i];
    for (i = 1, k = 2; k < n; i++, k <<= 1) {
        for (j = 0, sk = (k >> 1); j+k-1 < n; ++j, ++sk)
            st[i][j] = min(st[i-1][j],st[i-1][sk]);
    }
}
int query(int x, int y) // min of { val[x] ... val[y] }
{
    int bl = 31-__builtin_clz(y-x+1);
    return min(st[bl][x], st[bl][y-(1<<bl)+1]);
}
int main(){
    rep(i,N)val[i]=i;
    initrmq(N);
    rep(i,20){
        int c=rand()%60,d=rand()%100;
        while(d<c)d=rand()%100;
        printf("(%d %d): %d\n",c,d,query(c,d));
    }
}