SHARE
TWEET

Sparse Table

Rock-Lee Mar 24th, 2019 (edited) 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define MAXN 100010
  3. #define INF 1e9
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8. int arr[MAXN];
  9. int sptable[20][MAXN];
  10.  
  11. void build() {
  12.     for( int i = 0; i < n; i++ ) sptable[0][i] = i;
  13.  
  14.     for( int i = 1; (1 << i) <= n; i++ ) {
  15.         for( int j = 0; j + ( 1 << i ) <= n; j++ ) {
  16.             if (arr[sptable[i-1][j]] < arr[sptable[i-1][j + (1 << (i-1))]]){
  17.                 sptable[i][j] = sptable[i-1][j];
  18.             }
  19.             else {
  20.                 sptable[i][j] = sptable[i-1][j + (1 << (i-1))];
  21.             }
  22.         }
  23.     }
  24. }
  25.  
  26. int query( int l, int r ) {
  27.     if(l > r) swap( r, l );
  28.     int size = r - l + 1;
  29.     int logOfSize = __builtin_clz(1) - __builtin_clz(size);
  30.     return min( arr[sptable[logOfSize][l]], arr[sptable[logOfSize][r - (1 << logOfSize) + 1 ]] );
  31. }
  32. int main() {
  33.  
  34.     int q, l, r;
  35.  
  36.     scanf( "%d", &n );
  37.     for( int i = 0; i < n; i++ ) {
  38.         scanf( "%d", &arr[i] );
  39.  
  40.     }
  41.     for(int i = 0; i < 20; i++) {
  42.         // arr[i] = INF;
  43.         for(int j = 0; j < n   ; j++) {
  44.             sptable[i][j] = INF;
  45.         }
  46.     }
  47.     build();
  48.     scanf( "%d", &q );
  49.     for( int i = 0; i < q; i++ ) {
  50.         scanf("%d %d", &l, &r);
  51.         printf("%d\n", query(l, r));
  52.     }
  53.  
  54.    
  55.     return 0;
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top