前言

最近学文化课学傻了，来复习一下数据结构。

能够实现区间操作的数据结构其实并不多，平常也就能用到这几个：

ST 表
树状数组
线段树
分块

今天我就只说这几个，方便新手入门。如果你是学数据结构的新手，一定一定要循序渐进，这几个数据结构是提高组很常考的考点。

ST 表

前置知识：倍增，动态规划
适用范围：RMQ 问题，区间 GCD 问题等
模板题：P3865，P1890

例题 1：P3865

题目大意

给定长度为

n

的序列

a

，以及

m

组询问，每次询问给出

l,r

，求

\max\{a_l,a_{l+1},\dots,a_r\}

。

1 \le n \le 10^5

，

1 \le m \le 2\times 10^6

。

题解

题目要求每次查询

O(1)

，最简单的想法就是预处理每个区间的最大值，这样时间确实合理，但空间复杂度

O(n^2)

，直接炸掉。

我们确实需要预处理，但预处理方式有不同。我们学校古时候有个 OIer 叫做 CEXE 的说过，“题目中有预处理，要么倍增，要么 dp”。根据倍增思想，我们定义

f_{i,j}

为从第

i

个元素开始的

2^j

个元素中的最大值。

i

的遍历范围明显是

1

到

n

，

j

一般从

1

到

30

。

接着推转移方程。根据倍增的特点，长度为

2^j

的区间可以由两个长度为

2^{j-1}

的区间拼起来。由于

j

从小到大遍历，长度为

2^{j-1}

的两个区间最大值已经知道，对这两个区间的两个最大值再取一个更大的即可。

这两个区间的最大值都该怎么获取呢？左边区间的起点显然与当前区间的起点相同，长度为

2^{j-1}

；右边区间的起点是左边区间的终点加一，左边区间的终点是

i+2^{j-1}-1

，所以右边区间的起点就是

i+2^{j-1}

，长度依然为

2^{j-1}

。我们就可以得到状态转移方程了。

f_{i,j}=\max(f_{i,j-1},f_{i+2^{j-1},j-1})

把它变成代码，就是

CPP

f[i][j]=max(f[i][j-1],f[min(i+(1<<(j-1)),n)][j-1]);

注意右边区间的起点可能超过

n

，要与

n

取一个更小值。

最后，不要忘记

f

数组的初始化。不难想到

f_{i,0}=a_i

，即从

i

开始的

2^0=1

个元素中的最大值就是

a_i

。后面的代码中我直接把输入内容存到了

f_{i,0}

中，没有开

a

数组。

预处理完了，来想如何

O(1)

算出答案。我们可以想到，对于询问区间

[l,r]

，可以把它拆成两个可以部分重叠的区间，一个从

l

开始往前覆盖，一个从

r

开始往后覆盖。由于重叠的部分对区间最大值没有影响，所以不用处理重叠部分。

例如，对于序列

a={1,1,4,5,1,4}

，假设我们已经预处理完了

f

数组，想要求

[2,6]

区间内的最大值。我们知道

f

数组如下：

	$i=1$	$i=2$	$i=3$	$i=4$	$i=5$	$i=6$
$j=0$	$1$	$1$	$4$	$5$	$1$	$4$
$j=1$	$1$	$4$	$5$	$5$	$4$	$4$
$j=2$	$5$	$5$	$5$	$5$	$4$	$4$

我们令

k=\left \lfloor \log_2 (r-l+1) \right \rfloor=2

。这有什么用呢？这表示我们可以用

[l,2^k]

和

[r-2^k+1,2^k]

来凑出

[l,r]

区间的最大值。例如

[2,6]

的最大值就是

\max(f_{2,2},f_{3,2})=5

。写成代码，就是

CPP

max(f[l][k],f[r-(1<<k)+1][k])

想要求出

k

，我们可以使用 cmath 头文件自带的函数 log2() 来取对数。注意函数返回值是 double 类型，需要强制转化成 int 类型，这样省下了一个下取整。

CPP

int k=log2(r-l+1);

最后的代码实现还有细节，由于我们要从长度小的区间推到长度大的区间，我们需要保证长度小的区间都预处理完成，所以我们必须先枚举

j

再枚举

i

。

下面是模板题 P3865 的主要代码。

CPP

cin>>n>>m;
for(int i=1;i<=n;i++){
	cin>>a[i][0];
}
for(int j=1;j<20;j++){
	for(int i=1;i<=n;i++){
		a[i][j]=max(a[i][j-1],a[min(i+(1<<j-1),n)][j-1]);
	}
}
while(m--){
	cin>>l>>r;
	int k=log2(r-l+1);
	cout<<max(a[l][k],a[r-(1<<k)+1][k])<<endl;
}

最后分析时间复杂度。预处理的复杂度为

O(n)

，每次查询复杂度

O(1)

，

m

次共

O(m)

，总复杂度

O(n+m)

，可以通过本题。

还有一个细节，log2() 函数的复杂度稍大于

O(1)

，但一般忽略。要是想做到严格

O(1)

，可以预处理出每个

\log_2 i

的值。

区间数据结构从入门到普及-

文章操作

前言

ST 表

例题 1：P3865

题目大意

题解

相关推荐

评论

区间数据结构从入门到普及-