ST表
最近刷题有点疯狂,写篇ST表冷静一下,顺便回顾一下。
什么是ST表
傻子或大犇都会看的定义
ST表是一种用于解决区间最值问题的数据结构,它的全称是Sparse Table,意为稀疏表。它的主要思想是预处理出每个区间的最值,然后通过预处理的结果来快速求出任意区间的最值。
有点蒙? 没关系,我当初也是,下面我会十分详细的一步一步推导。
从求最大值说起…
现在有一个序列a,我们想要求出区间$[l,r]$的最大值,请问该怎么做?
想必大家都会想到枚举这一优美且高效(搞笑)的方法,所以我们不妨试一试。
方法自然是从$a[l]$开始枚举到$a[r]$,每两个数取最大值,最后得到的就是区间$[l,r]$的最大值。1
2
3int ans = a[l];
for(int i = l + 1; i <= r; i++)
ans = max(ans, a[i]);
真逝完美!
来分析一下时间复杂度,每次枚举需要$O(1)$,总共需要枚举$r-l+1$次,所以总时间复杂度为$O(n)$。还算过得去,对吧?但是,出题老师不可能放你暴力过的,倘若ta轻描淡写地来一句 “n组询问,每组一个[l,r]“,那就惨了,代码就被迫变成了这样:1
2
3
4
5
6int ans = a[l];
for(int i = 1;i <= n;i++)
int l, r;
cin >> l >> r;
for(int j = l;j <= r;j++)
ans = max(ans, a[j]);
这样的时间复杂度就是$O(n^2)$了,显然是不可接受的。为了解决这个问题,ST表应运而生。
ST表的过程
ST表只有两个步骤,第一个是$O(n\log{n})$的预处理,第二个是$O(1)$的查询。显然比暴力要快得多。
预处理
预处理用到了动态规划的思想,我们定义一个二维数组 $st$ ,其中 $st_{ij}$ 表示从 $a_i$ 开始,长度为 $2^j$ 的区间的最大值。也就是区间$[i,i+2^j-1]$的最大值。
接下来便是构造动态转移方程,在构造之前,先来看看求最大值这件事的一个性质:
这个性质很好理解,就是把一个区间分成两个区间,然后求两个区间的最大值,最后再求两个最大值的最大值,就是整一个大区间的最大值。这样就把一个大区间的最大值转化成了两个小区间的最大值。
这么说……撕,那转移方程不就有了吗?对于$[i,i+2^j-1]$的最大值,就有:
而:
所以:
这样转移方程不就出来了么?1
2
3
4
5for(int i = 1;i <= n;i++)//枚举起点
st[i][0] = a[i];
for(int j = 1;j <= \log2(n);j++)//枚举区间长度
for(int i = 1;i + (1 << j) - 1 <= n;i++)//枚举起点
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);//(1 << j) = 2^j
查询
查询的时间复杂度度是$O(1)$的。既然我们已经预处理出所有起点的所有长度为$2^j$的区间的最大值,如果我们要查询$max([l,r])$,其实只需要找到这段区间所对应的$st{lx}$就行了。在区间和$st$表中,$l$和$i$的意义都是一样的,所以$i$就是$l$,而$x$也不难推导,我们知道$st{ix}$就是$max([i,i+2^x-1])$,而我们要查询$max([l,r])$,所以
因为$i=l$,所以
确实
由于$\log$函数的值是浮点数,向下取整可能导致查询的区间长度不够,向上取整又可能多查了,这怎么办?
在预处理的时候提出了一个性质:
把它稍微改一下:
也就是说,就算被拆成的两个区间有重叠,只要它俩能填满整个区间,那么这整个区间的最大值就是这两个区间的最大值的最大值。这样就可以解决上面的问题了,我们只需要对$x=\log(r-l+1)$向下取整,即
然后用$r-(2^x-1)$,记为$d$,就是这一段
如图3所示,$[l,x]$和$[d,r]$的长度都是$2^x$,所以我们可以直接用$st{lx}$和$st{dr}$来代替$max([l,r])$,也就是
代码:1
2
3
4int find(int l,int r){
int x=Log2[r-l+1];
return max(st[l][x],st[r-(1<<x)+1][x]);
}
小优化
上面的代码还是有点慢,因为$\log$函数是$O(\log{n})$的,所以我们可以用一个数组来存储$\log$函数的值,这样就不用每次都要调用$\log$函数了。1
2for(int i = 2; i <= n; i++)
Log2[i] = Log2[i >> 1] + 1;
ST表的应用
通过上面的例子,很容易看出ST表在求最大值的时候的优越性,但是ST表不仅仅可以求最大值,还可以求最小值,甚至是求区间和,区间异或和等等。
其实,这一类问题都被称为可重复贡献问题,定义就是对于运算$opt$,有$x$ $opt$ $x=x$,像$max(x,x)=x,min(x,x)=x$等。
但ST表也有它的不足,比如它只能维护少量信息,而且不支持修改。
几道破题
P3865 【模板】ST表
1 |
|
没啥好说的,就是模板题,不过这题的数据强度不低,记得用快速读入。
P2880 [USACO07JAN] Balanced Lineup G
1 |
|
同样没啥好说的,最大值和最小值同时求就好。