SparseTable Class (C++)

SparseTable.h

#include <cstdio>

using namespace std;

#ifndef maxn
  #define maxn 150000  //default maxn=150000
#endif

class SparseTable {
	private:
		int table[maxn][32];

	public:
		int data[maxn],n;
		virtual int cmp(int p, int q) {  //default: Range-Min-Query
			return p<q?p:q;          //you have to inherit my class
		}                                //and give your own cmp function
		void build(void) {
			int m=lg2(n);
			for (int i=1; i<=n; i++) table[i][0]=data[i];
			for (int i=1; i<=m; i++) 
				for (int j=1; j<=n; j++) 
					table[j][i]=cmp(table[j][i-1],table[(j+(1<<(i-1)))][i-1]);
		}
		int query(int p, int q) {
			int m=lg2(q-p+1);
			return cmp(table[p][m],table[q-(1<<m)+1][m]);
		}
#ifdef DEBUG	//an easter egg
		void print() {
			for (int i=1; i<=n; i++) printf("%d",table[i][1]);
			printf("\n");
		} 
#endif
};