二维ST表学习笔记

众所周知,ST表是一种离线解决RMQ(区间最值)问题的方法。

可以在O(n log n)的时间内进行预处理,然后在O(1)时间内查询到结果。

我们先来复习一下,一维st表的预处理和查询过程。

对于预处理,我们先定义一个名为st的二维数组,其中st[i][j]表示以i为起点,从起点开始(含起点)往后2^j个元素的最值。

满足i+2^j-1不越界

因为2^0=1,因此st[i][0]=a[i]

然后我们用2个for循环去打表就行了

接着是查询,这里我画了个图来解释。

其中橙色的线表示两个区间。

int st[50001][16];
int a[50001];//用于存储原有的数据
int pow2(int x) {
    return 1 << x;//相当于计算2的x次方,使用位运算
}
void init_st(int n) {
    for (int i=1;i<=n;i++) st[i][0]  = a[i];
    for (int j=1;pow2(j)<=n;j++) 
        for (int i=1;i+pow2(j)-1<=n;i++) st[i][j] = min(st[i][j-1],st[i+pow2(j-1)][j-1]);
}
int query(int l,int r) {
    int k = log2(r - l + 1);
    return min(st[l][k],st[r-pow2(k)+1][k]);
}
int main() {
    return 0;
}

接着是二维ST表

与一维ST表不同的是,我们这么定义数组。

int st[50001][50001][16][16];

其中,对于st[i][j][k][l],用于表示以(i,j)为起点,一直到(i+pow2(k)-1,j+pow2(l)-1)这个点的矩形内的最值。

那么,我们如何做预处理和查询呢。

显然,由于变成了4维数组,我们得把for循环写成这样

for (int i=0;i<=log2(n);i++)
    for (int j=0;j<=log2(m);j++) {
        if (i == 0 && j == 0) continue;
        for (int x=1;x<=n;x++) 
            for (int y=1;y<=m;y++) {
                // ....
            }

其中,st[x][y][0][0]为原来的值。

这里,我用i和j分别表示x和y方向的范围(以2为底的指数表示)

接着,我们想想,既然我们推的过程是

优先递增j,而后递增i

也就意味着,我们可以对i的值分类讨论

①对于i==0的情况,我们可以从i不变,j-1的状态转移

st[x][y][i][j] = max(st[x][y][ i ][j-1],st[     x     ][y+pow2(j-1)][ i ][j-1]);

②对于i>0的情况,我们可以从j不变,i-1的状态转移

st[x][y][i][j] = max(st[x][y][i-1][ j ],st[x+pow2(i-1)][     y     ][i-1][ j ]);

所以,最终的预处理代码就变成了这样

int pow2(int x) {
	return 1 << x;//相当于计算2的x次方,使用位运算
}
void init() {
	//st[x][y][0][0]已经预先填充
	for (int i=0;i<=log2(n);i++)
		for (int j=0;j<=log2(m);j++) {
			if (i == 0 && j == 0) continue;
			for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) {
				int rangex = x + pow2(i) - 1;
				int rangey = y + pow2(j) - 1;
				if (rangex > n || rangey > m) continue;
				if (i == 0) {
					st[x][y][i][j] = max(	st[x][		y		][i][j-1],
											st[x][y+pow2(j-1)	][i][j-1]);
				}
				else {
					st[x][y][i][j] = max(	st[		x		][y][i-1][j],
											st[x+pow2(i-1)	][y][i-1][j]);
				}
			}
		}
}

那么,同理,查询我们也可以分为4块。分别是左上,左下,右上,右下

int query_max(int x1,int y1,int x2,int y2) {
	int k1 = log2(x2-x1+1);
	int k2 = log2(y2-y1+1);
	return max(
				max(
					st[      x1     ][y1][k1][k2],
					st[x2-pow2(k1)+1][y1][k1][k2]
					),
				max(
					st[x1][y2-pow2(k2)+1][k1][k2],
					st[x2-pow2(k1)+1][y2-pow2(k2)+1][k1][k2]
					)
				);
}

这里附上一道二维st表的例题和我的题解代码:

HDU 2888 Check Corners

https://github.com/cyyself/OILife/blob/master/HDU/2888%20-%20Check%20Corners.cpp

发表评论

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

Back to Top