【倍增】RMQ-ST算法

RMQ:Range Minimum/Maximum Query,即区间最值问题。

给定n组询问,每组询问由左端点l,右端点r组成,问区间[l,r]的最值。

朴素的算法是O(n^{2}\log n)的,排序,,,;

稍微动点脑子可以做到O(n^{2}),枚举左右端点,单组O(n),n组O(n^{2})

还有ST算法(Sparse Table),实质上是动态规划,可以做到单组O(\log n)预处理,O(1)的查询,总复杂度O(n\log n)

以及线段树。

当然正解是建立笛卡尔树,这个坑后面再填。

 

ST算法

动态规划思想,令f[i][j]为数列A,在区间[i][i + (1 << j) – 1]的最大值,即从i开始的(1 << j)个数的最大值,显然递推边界是f[i][0] = A[i],即A在[i,i]内最大值。

在递推时咱们成倍增长子区间长度,有状态转移方程:

f[i][j] = max(f[i][j – 1],f[i + (1 << j)][j – 1]),即:

长度为(i << j)的区间内,左右半区间的最大值中较大的一个。

const int L = 666;

int f[L][L],A[L];
int n;

int max(int a,int b){
	return a > b ? a : b;
}

void STPrework(){
	for(int i = 1;i <= n;i++){
		f[i][0] = A[i];
	}
	int t = log(n) / log(2) + 1;
	for(int j = 1;j < t;j++){
		for(int i = 1;i <= n - (i << j) + 1;i++){
			f[i][j] = max(f[i][j - 1],f[i + (i << (j - 1))][j - 1]);
		}
	}
}

int STQuery(int l,int r){
	int k = log(r - l + 1) / log(2);
	return max(f[l][k],f[r - (1 << k) + 1][k]);
}

【例题】UVA11235 Frequent values

这个坑待填。

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

加入对话

1条评论

电子邮件地址不会被公开。 必填项已用*标注