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

· · 算法·理论

前言

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

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

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

ST 表

例题 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})

把它变成代码，就是

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。写成代码，就是

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

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

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

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

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

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 的值。