apache设置网站网址必应搜索引擎入口

【题目链接】

洛谷 P3865 【模板】ST 表 && RMQ 问题

【题目考点】

1. ST表

【解题思路】

本题是ST表模板题，主要介绍ST表的概念及写法。
实际作为RMQ问题可以使用ST表、线段树、树状数组、笛卡尔树等方法解决。

1. 在线算法与离线算法

• 在线算法：‌ 在线算法必须在‌输入序列逐步到达‌的过程中实时地做出决策。算法在接收到输入序列的一个元素时，必须在下一个元素到达之前，基于‌当前和之前的信息‌输出一个对应的结果。
  例：插入排序
• 离线算法：在开始执行‌之前‌就已经获知了‌完整‌的输入序列信息。算法可以基于对整个输入的全局视图进行分析和规划，然后一次性或逐步输出结果。
  例：选择排序

2. RMQ问题

RMQ问题(Range Maximum/Minimum Query)为区间最值查询问题，可以使用ST表、线段树、树状数组、笛卡尔树等方法解决。常用方法为ST表与线段树。

3. ST表

ST表（Sparse Table），又名稀疏表，是用来处理可重复的贡献问题的离线算法，是基于倍增思想的动态规划算法。
可以维护区间最值(RMQ)，区间gcd，区间按位与，区间按位或等。
由于ST表是离线算法，因而不能进行修改操作。

一、预处理ST表

输入的整数序列为$a$序列。
ST表为一个二维数组$f$，$f_{i,j}$表示$a$序列区间$[i,i+2^j-1]$中的最大值，也就是从$a_i$开始长为$2^j$的区间中元素的最大值。
由于f数组第二维为指数，解决算法问题用到的数组长度都不会超过$10^8$，已知$2^{30}\approx 10^9$，区间长度一定不会达到$10^9$，因此f数组第二维设为30就够用了。f数组第一维的长度为a序列的长度。
区间$[i,i+2^j-1]$可以划分为两个长为$2^{j-1}$的子区间，分别为$[i,i+2^{j-1}-1]$与$[i+2^{j-1},i+2^j-1]$。
区间$[i,i+2^{j-1}-1]$的最大值为$f_{i,j-1}$
区间$[i+2^{j-1},i+2^j-1]$的最大值为$f_{i+2^{j-1},j-1}$
所以区间$[i,i+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_{i+2^{j-1},j-1}\} fi,j​=max{fi,j−1​,fi+2j−1,j−1​}
已知$f_{i,0}$为区间$[i,i]$的最大值，也就是$a_i$，所以$f_{i,0}=a_i$
通过递推可以求出$f$数组。
注意：由于该递推式中等号右侧用到的元素第二维相比于j较小，而第一维存在大于i的值。因此外层循环控制变量为$j$，内层循环控制变量为i。
$a$序列长度为$n$，$f_{i,j}$表示a序列中一个长为$2^j$的区间中的最大值。因此有$2^j\le n$，即$j\le {\log }_{2}n$。由于$j$是整数，所以$j\le \lfloor {\log }_{2}n\rfloor$。

在C++中，除了使用<cmath>中的log或log2函数求对数，也可以通过递推求出所有可能用到的$\lfloor {\log }_{2}i\rfloor ,i\in [1,n]$
由于${\log }_{2}i={\log }_2(\frac{i}{2}\cdot 2)={\log }_2\frac{i}{2}+{\log }_{2}2={\log }_2\frac{i}{2}+1$
等号两边都向下取整，得：
$\lfloor {\log }_{2}i\rfloor =\lfloor {\log }_2\frac{i}{2}\rfloor +1$
已知$\lfloor {\log }_{2}1\rfloor =0$，可以递推求出$\lfloor {\log }_{2}i\rfloor ,i\in [1,n]$。

预处理f数组时，外层$0\le j\le \lfloor {\log }_{2}n\rfloor$。内层i最小为1，i最大时，区间右端点$i+2^j-1$达到n，所以满足$i+2^j-1\le n$。
已知C++中可以通过位运算1<<j求$2^j$。注意：左移运算符<<的优先级低于算术运算符。
根据以上描述，得到预处理ST表的代码：

const int N = 100005, LN = 30;
int a[N], lg[N], f[N][LN];//f[i][j]：a[i]~a[i+2^j-1]中的最大值 
void initST(int n)
{for(int i = 2; i <= n; ++i)lg[i] = lg[i/2]+1;//lg[i]：log2(i)向下取整for(int i = 1; i <= n; ++i)f[i][0] = a[i];for(int j = 1; j <= lg[n]; ++j)for(int i = 1; i+(1<<j)-1 <= n; ++i)f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}

预处理ST表的时间复杂度为$O(n\log n)$

二、区间查询最值

查询给定区间$[l,r]$中的最大值。
区间长度为$r-l+1$，一定存在一个区间长度为2的幂，满足小于等于$r-l+1$的长度最大的区间。
记该区间的长度为$k$，那么$k$满足$2^k\le r-l+1<2^{k+1}$。
因此$k\le {\log }_2(r-l+1)<k+1$，即$k=\lfloor {\log }_2(r-l+1)\rfloor$
取以$l$为左端点的长为$2^k$的区间$[l,l+2^k]$
取以$r$为右端点的长为$2^k$的区间$[r-2^k+1,r]$
由于$r-l+1<2^{k+1}=2\cdot 2^k$
所以$r+1-2^k<l+2^k$，即$l+2^k>r-2^k+1$
因此$[l,l+2^k]\cup [r-2^k+1,r]=[l,r]$
因此只要求出$[l,l+2^k]$中的最大值，以及$[r-2^k+1,r]$中的最大值，二者的最大值即为区间$[l,r]$中的最大值。
$[l,l+2^k]$中的最大值为$f_{l,k}$，$[r-2^k+1,r]$中的最大值为$f_{r-2^k+1,k}$
因此区间$[l,r]$中的最大值为 max ⁡ { f l , k , f r − 2 k + 1 , k } \max\{f_{l, k}, f_{r-2^k+1, k}\} max{fl,k​,fr−2k+1,k​}
写成代码为：

int query(int l, int r)
{int k = lg[r-l+1];return max(f[l][k], f[r-(1<<k)+1][k]);
}

使用ST表进行区间查询最值的时间复杂度为$O(1)$。

【题解代码】

解法1：ST表

#include<bits/stdc++.h>
using namespace std;
const int N = 100005, LN = 30;
int a[N], lg[N], f[N][LN];//f[i][j]：a[i]~a[i+2^j-1]中的最大值 
void initST(int n)
{for(int i = 2; i <= n; ++i)lg[i] = lg[i/2]+1;for(int i = 1; i <= n; ++i)f[i][0] = a[i];for(int j = 1; j <= lg[n]; ++j)for(int i = 1; i+(1<<j)-1 <= n; ++i)f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}
int query(int l, int r)
{int k = lg[r-l+1];return max(f[l][k], f[r-(1<<k)+1][k]);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r;cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> a[i];initST(n);for(int i = 1; i <= m; ++i){cin >> l >> r;cout << query(l, r) << '\n';}return 0;
}