RMQ(Sparce Table)

#include<bits/stdc++.h>
using namespace std;

#define si(n) scanf("%d",&n)
#define MAX 100005

int arr[MAX],M[MAX][17];

void sparce(int n){
    int i,j;
    for(i=0;i<n;i++)
        M[i][0]=i;
    for(j=1;1<<j <= n;j++){
        for(i=0;i+(1<<j)-1 <n;i++){
            if(arr[M[i][j-1]]<arr[M[i+(1 << (j-1))][j-1]])
                M[i][j]=M[i][j-1];
            else
                M[i][j]=M[i+ (1<<(j-1))][j-1];
        }
    }
}

int RMQ(int i,int j){
    int k=log2(j-i+1);
    if(arr[M[i][k]]<=arr[M[j-(1<<k)+1][k]])
        return M[i][k];
    else
        return M[j-(1<<k)+1][k];
}

int main()
{

    int n,i,j;
    si(n);
    for(i=0;i<n;i++)
        si(arr[i]);
    sparce(n);
    cout<<"BUILD"<<endl;
    for(;;){
        cout<<"input : ";
        si(i);si(j) ;
        cout<<RMQ(i,j)<<endl;
    }
}