sparse_table.cpp

//sparse_table
//complexity:
//  min_range - O(1)
//  build - O(n * log n)

const int N = 100002;
const int LogN = 18;
int st[N][LogN];
int n;

void build(int a[]){
   
    for(int i = 0; i < n; ++i)
      st[i][0] = a[i];
  
    for(int k = 1; k < LogN; ++k)
      for(int i = 0; i + (1<<k) < n; ++i)
        st[i][k] = min(st[i][k-1], st[i+(1<<k-1)][k-1]);
}

int min_range(int l, int r){
   int k = 31 - __builtin_clz(r - l + 1);
   return min(st[l][k], st[r-(1<<k)+1][k]);
}