POJ 3264 Balanced Lineup ST算法

ST算法即是sparse table算法，就是稀疏表的意思，就是利用二分法来划分一个表，划分为2的次方段，之后利用这个st表计算查询结果，能够使得预处理时间O(nlgn)，而查询时间为O(1) ；

那么有人会有疑问。既然查询时间是O(1)。那么为什么这个算法非常多时候并不比线段树快多少。甚至根本没有快过呢？

由于事实上查询时间为O(log(range))， range为查询区间的大小，由于要找到range二进制的最高位数，能够使用floor(log(range))的数学方法查找这个数。只是也是须要lg(rang)的时间效率。由于range不算太大。故此这点时间效率能够觉得是O(1).只是这就解析了为什么这个算法的查询时间不比线段树快多少。由于线段树的查询时间就是log(range)。

网上非常少人指出指点，一般都是笼统地说查询时间是O(1), 好像也不少人为此感到疑惑，故此解析下。

只是也能够这么说算法本身的查询时间效率是O(1)。而实际运行起来却是 O(logn)。或者说理论上的时间效率是O(1)，实际时间效率是O(logn)。

预计这就是为什么非常多大牛的博客或者一些书本上也是写这个算法的查询效率是O(1)了。

说究竟就是一个数学方法计算。

详细能够參考topcoder或者參考这个大牛的吧：http://blog.csdn.net/v_july_v/article/details/18312089

本算法的优势就是代码量会比线段树省点。

掌握了当中的数学原理之后，这个算法还是非常好写的。

只是有线段树的存在，那么这个算法好像也不是不可缺少的。

#include <cstdio>
#include <algorithm>

const int MAX_N = 50001;
const int L = 17;//16;//(int)log(MAX_N) / log(2) + 1;
int N, Q, A, B;
int maxArr[MAX_N][L], minArr[MAX_N][L];

void initRMQ_ST()
{
	for (int j = 1; j < L; j++)
		for (int i = 1; i <= N; i++)
		{
			if (i - 1 + (1<<j) <= N)
			{
				maxArr[i][j]=max(maxArr[i][j-1], maxArr[i+(1<<(j-1))][j-1]);
				minArr[i][j]=min(minArr[i][j-1], minArr[i+(1<<(j-1))][j-1]);
			}
			else break;//能够break掉
		}
}

inline int query(int low, int up)
{
	int range = up - low + 1;
	int r = 0;
	while ((1<<(r+1)) <= range) r++;
	int maxV = max(maxArr[low][r], maxArr[up-(1<<r)+1][r]);
	int minV = min(minArr[low][r], minArr[up-(1<<r)+1][r]);
	return maxV - minV;
}

int main()
{
	while (scanf("%d %d", &N, &Q) != EOF)
	{
		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &maxArr[i][0]);
			minArr[i][0] = maxArr[i][0];
		}
		initRMQ_ST();
		while (Q--)
		{
			scanf("%d %d", &A, &B);
			printf("%d\n", query(A, B));
		}
	}
	return 0;
}