sparse_table_algorithm.cpp

RMQ的sparse table算法的实现

/*A better approach is to preprocess RMQ for sub arrays of length 2k using dynamic programming.
 We will keep an array M[0, N-1][0, logN] where M[i][j] is the index of the minimum value in the sub array starting 
 at i having length 2j. */

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

const int MAXN=128;
const int LOGMAXN=7;

int M[MAXN][LOGMAXN];
int A[MAXN];
int N;

void sparse_table()
{
	int i,j;
	//initialize M for the intervals with length 1
	for(i = 0; i < N; ++i)
		M[i][0] = i;
	//compute values from smaller to bigger intervals
	for(j = 1;(1 << j) <= N; ++j)
		for(i = 0;i + (1 << j) - 1 < N; ++i)
			if (A[M[i][j-1]] < A[M[i + (1 << (j - 1))][j - 1]])
				M[i][j] = M[i][j-1];
			else
				M[i][j] = M[i + (1 << (j - 1))][j - 1];
}

int RMQ(int i ,int j)
{
	int k = (int)(log(j-i+1)/log(2));
	if(A[M[i][k]]<A[M[j-(1<<k)+1][k]])
		return M[i][k];
	else return M[j-(1<<k)+1][k];
}

int main()
{
	N=10;// 一共几个数
	int a,b;
	sparse_table();
	while(cin>>a>>b)
	{
		cout<<RMQ(a,b)<<endl;
	}
	return 0;
}