gistfile1.cpp

//given A[0..(N-1)], compute Q queies of min(A[i..j]) in O(QlgN+NlgN)
int A[MAXN], a[MAXL][MAXN]; // MAXL = log(MAXN)+1
void buildTree()
{
	for(int i = 0; i < N; i++)
		a[0][i] = A[i];
	L = int(log2(N))+1;
	for(int k = 0; k < L; k++)
	{
		for(int i = 0; i < N; i++)
			a[k+1][i] = min(a[k][i], a[k][i+(1<<k)]);
	}
}
int findMin(int i, int j)
{
	for(int l = 0; ; l++)
	{
		if(j-i <= (1<<l))
			return min(a[l][i], a[l][j-(1<<l)+1])
	}
}