二维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循环去打表就行了

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

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

接着是二维ST表

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

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

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

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

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

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

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

优先递增j,而后递增i

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

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

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

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

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

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

HDU 2888 Check Corners

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

发表评论

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

Back to Top