SparseTable.h

   1 #include <cstdio>
   2
   3 using namespace std;
   4
   5 #ifndef maxn
   6   #define maxn 150000  //default maxn=150000
   7 #endif
   8
   9 class SparseTable {
  10         private:
  11                 int table[maxn][32];
  12
  13         public:
  14                 int data[maxn],n;
  15                 virtual int cmp(int p, int q) {  //default: Range-Min-Query
  16                         return p<q?p:q;          //you have to inherit my class
  17                 }                                //and give your own cmp function
  18                 void build(void) {
  19                         int m=lg2(n);
  20                         for (int i=1; i<=n; i++) table[i][0]=data[i];
  21                         for (int i=1; i<=m; i++)
  22                                 for (int j=1; j<=n; j++)
  23                                         table[j][i]=cmp(table[j][i-1],table[(j+(1<<(i-1)))][i-1]);
  24                 }
  25                 int query(int p, int q) {
  26                         int m=lg2(q-p+1);
  27                         return cmp(table[p][m],table[q-(1<<m)+1][m]);
  28                 }
  29 #ifdef DEBUG    //an easter egg
  30                 void print() {
  31                         for (int i=1; i<=n; i++) printf("%d",table[i][1]);
  32                         printf("\n");
  33                 }
  34 #endif
  35 };