data-structure - Sparse Table(RMQ)

/*
    Range Minimum Query (Sparse Table).
    Preprocess(O(nlogn),Query(O(1))
    Indexing- [1,n].
*/
int dp[N][22];
int mn[N];
void initRMQ(int n,int a[])
{
    mn[0]=-1;
    for(int i= 1;i<=n;i++) dp[i][0] = a[i], mn[i]=mn[i/2]+1;
    for(int j= 1; (1<<j) <= n; j ++ ){
        for(int i = 1; i + (1<<j) - 1 <= n ; i ++ ) {
            dp[i][j] = min(dp[i][j-1] , dp[i + (1<<(j-1))][j-1]);
        }
    }
}
int askRMQ(int L,int R)
{
    int k = mn[R-L+1];
    return min(dp[L][k], dp[R - (1<<k) + 1][k]);
}
/*======================================================================*/