Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 其它算法, 动态规划 » , , ,

RMQ问题的ST算法

RMQ问题(Range Minimum/Maximum Query,区间最值问题),是指给定一个长度为n的数列A,回答若干次询问RMQ(A,i,j)(i,j<=n)(通常次数非常巨大),每次返回数列A中下标在i,j里的最小(大)值。
RMQ问题解法很多,如朴素算法、线段树、ST算法RMQ与LCA互相转化等,不同算法思想及复杂度均有所差异。本文主要讲解其中非常高效的稀疏表算法(Sparse Table,ST算法)。

一 算法思想

ST(Sparse Table,稀疏表)算法是求解RMQ问题的经典在线算法,以O(nlogn)时间预处理,然后在O(1)时间内回答每个查询。

ST算法本质上是动态规划算法,定义了一个二维辅助数组st[n][n],st[i][j]表示原数组a中从下标i开始,长度为2^j的子数组中的最值(以最小值为例)。

要求解st[i][j]时,即求下标i开始,长度为2^j的子数组的最小值时,可以把这段子数组再划分成两半,每半的长度为2^(j-1),于是前一半的最小值为st[i][j-1],后一半的最小值为st[i+2^(j-1)][j-1],于是动态规划的转移方程为:

st[i][j] = min(st[i][j-1], st[i+2^(j-1)][j-1])

长度为2^j的情况只和长度为2^(j-1)的情况有关,只需要初始化长度为2^0=1的情况即可。而长度为1时的最小值是显然的(为其本身)。

现在问题是,st数组可以怎样加速我们的查询呢?

这也是算法的巧妙之处,假设求下标在u到v之间的最小值。先求u和v之间的长度len=v-u+1,然后求k=log2(len),则u到v之间的子数组可以分为两部分:

  • 以u开始,长度为2^k的一段
  • 以v结束,长度为2^k的一段(可以计算得到起始位置为v-2^k+1)

注意,一般情况下这两段是重叠的,但是这两段的最小值中较小的一个仍然是u到v的最小值。于是

RMQ(u,v) = min(st[u][k], st[v-2^k+1][k])

二 算法实现

算法的一个实现方法如下。

其中使用位运算替代2的幂次的计算,加快运算速度。

使用时需要先调用initRMQ()进行初始化,然后再调用RMQ(u,v)进行查询。

const int mx = 10000 + 10;  //数组最大长度
int n, a[mx]; //数组长度,数组内容

int st[mx][30]; //DP数组
void initRMQ()
{
	for (int i = 0; i < n; i++) st[i][0] = a[i];
	for (int j = 1; (1 << j) <= n; j++) //使用位运算加速
		for (int i = 0; i + (1 << j) - 1 < n; i++)
			st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}

int RMQ(int u, int v)
{
	int k = (int)(log(v-u+1.0) / log(2.0)); //类型转换优先级高,除法整体要加括号
	return min(st[u][k], st[v-(1<<k)+1][k]);
}

有时候需要得到最值的下标而不是最值内容,这时可以使用以下的下标版本。

const int mx = 10000 + 10;  //数组最大长度
int n, a[mx]; //数组长度,数组内容

int st[mx][30]; //DP数组
void initRMQIndex() 
{
	for (int i = 0; i < n; i++)		st[i][0] = i;
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 0; i + (1 << j) - 1 < n; i++)
			st[i][j] = a[st[i][j-1]] < a[st[i+(1<<(j-1))][j-1]] ? 
									st[i][j-1] : st[i+(1<<(j-1))][j-1];
}

int RMQIndex(int s, int v) //返回最小值的下标
{
	int k = int(log(v-s+1.0) / log(2.0));
	return a[st[s][k]] < a[st[v-(1<<k)+1][k]] ? st[s][k] : st[v-(1<<k)+1][k];
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论