Sparse Table Data Structure

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
///length of array = n ;

ll n,a[200005];
ll st[32][200005];
void sparsetable()
{
    ll i,j,x,y;

    for(i=0; i<n; i++) st[0][i]=i;

    for(i=1; (1<<i)<n; i++)
    {
        for(j=0; j+(1<<i)<=n; j++)
        {
            x=st[i-1][j];
            y=st[i-1][j+(1<<i-1)];
            if(a[x]<=a[y]) st[i][j]=x;
            else  st[i][j]=y;
        }
    }
}


ll range_query(ll l,ll r)
{
    ll k=log2(r-l);
    ll x=st[k][l];
    ll y=st[k][r-(1<<k)+1];

    if(a[x]<=a[y]) return x;
    else return y;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll i,j,k,l,q;

    cin>>n;

    for(i=0; i<n; i++) cin>>a[i];

    sparsetable();


    cin>>q;

    while(q--)
    {
         cin>>j>>l;

         cout<<a[range_query(j,l)]<<endl;
    }

    return 0;
}