RMQ Sparse table

Sparse table

Code

void init(int *A){
	for(int i=1;i<=n;++i) rmq[0][i]=A[i];
	for(int i=1;(1<<i)<=n;++i) 
		for(int j=1;j+(1<<i)-1<=n;++j)
			rmq[i][j]=max(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
 
int get(int L,int R){
	int k=log2(R-L+1);
	return max(rmq[k][L],rmq[k][R-(1<<k)+1]);
}

• void init(int *array): initialize the sparse table with the passed array.
• int get(int L, int R): Return the max/min value in range [L, R].