Advertisement
Saleh127

Sparse Table Data Structure

Oct 7th, 2021
1,118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5. ///length of array = n ;
  6.  
  7. ll n,a[200005];
  8. ll st[32][200005];
  9. void sparsetable()
  10. {
  11.     ll i,j,x,y;
  12.  
  13.     for(i=0; i<n; i++) st[0][i]=i;
  14.  
  15.     for(i=1; (1<<i)<n; i++)
  16.     {
  17.         for(j=0; j+(1<<i)<=n; j++)
  18.         {
  19.             x=st[i-1][j];
  20.             y=st[i-1][j+(1<<i-1)];
  21.             if(a[x]<=a[y]) st[i][j]=x;
  22.             else  st[i][j]=y;
  23.         }
  24.     }
  25. }
  26.  
  27.  
  28. ll range_query(ll l,ll r)
  29. {
  30.     ll k=log2(r-l);
  31.     ll x=st[k][l];
  32.     ll y=st[k][r-(1<<k)+1];
  33.  
  34.     if(a[x]<=a[y]) return x;
  35.     else return y;
  36. }
  37.  
  38. int main()
  39. {
  40.     ios_base::sync_with_stdio(0);
  41.     cin.tie(0);
  42.     cout.tie(0);
  43.  
  44.     ll i,j,k,l,q;
  45.  
  46.     cin>>n;
  47.  
  48.     for(i=0; i<n; i++) cin>>a[i];
  49.  
  50.     sparsetable();
  51.  
  52.  
  53.     cin>>q;
  54.  
  55.     while(q--)
  56.     {
  57.          cin>>j>>l;
  58.  
  59.          cout<<a[range_query(j,l)]<<endl;
  60.     }
  61.  
  62.     return 0;
  63. }
  64.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement