基于ST表的RMQ算法

作者: zqqian 分类: ACM,算法 发布时间: 2017-08-09 23:46

基于ST表的RMQ算法可以在O(1)的时间复杂度内计算出一个区间内的最值。

基本思想是将一段长度中的最值保存下来。查询的时候直接返回。避免了常规算法中的一次一次比较的操作。

详细请参考书籍:《算法竞赛入门经典训练指南》–刘汝佳

这里仅谈论我自己的理解。


对于长度为n的数组,我们可以知道其二叉树深度不会超过log2 n。

此时就可以创建一个二维数组d[n][logn]。

d[i][j]代表以i为起点,长度为2^j区间上的最值。

在输入进数组之后,首先将d[i][0]赋值为a[i],

然后使用循环,计算出以i为起点,不同长度区间上的值

for(int j = 1; n-(1 << j) >= 0; j++) {
	// warning! this is j !

	for(int i = 1; i <= (n - (1 << j)); i++) {
		//从0-(n - (1 << j))为起点才有相应的长度,n - (1 << j)之后为起点到末尾的长度就不够了。

		d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
		// d[i][j]存储的是以i为起点,长度为2^j的区间内的最大值

	}
}

 

以上就是预处理操作。

 

 

而查询[l,r)区间内的最大值的操作为

 

 

int query(int l, int r) {

	int x = 0;

	while(l + (1 << x) < r + 1) { // find the max of x which 2^x <= length;

		x++;

	}

	return max(d[l][x], d[r - (1 << x) + 1][x]); // warning ! this must  is r-(1<<x)+1 !

}

 

发表评论

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