网站开发的目的及意义,网站开发主要任务,国外自助建站系统,开发公司工程部技术负责人职责【题目链接】
洛谷 P3865 【模板】ST 表 RMQ 问题
【题目考点】
1. ST表
【解题思路】
本题是ST表模板题#xff0c;主要介绍ST表的概念及写法。 实际作为RMQ问题可以使用ST表、线段树、树状数组、笛卡尔树等方法解决。
1. 在线算法与离线算法
在线算法 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 a a序列。 ST表为一个二维数组 f f f f i , j f_{i,j} fi,j表示 a a a序列区间 [ i , i 2 j − 1 ] [i, i2^j-1] [i,i2j−1]中的最大值也就是从 a i a_i ai开始长为 2 j 2^j 2j的区间中元素的最大值。 由于f数组第二维为指数解决算法问题用到的数组长度都不会超过 10 8 10^8 108已知 2 30 ≈ 10 9 2^{30}\approx10^9 230≈109区间长度一定不会达到 10 9 10^9 109因此f数组第二维设为30就够用了。f数组第一维的长度为a序列的长度。 区间 [ i , i 2 j − 1 ] [i, i2^j-1] [i,i2j−1]可以划分为两个长为 2 j − 1 2^{j-1} 2j−1的子区间分别为 [ i , i 2 j − 1 − 1 ] [i,i2^{j-1}-1] [i,i2j−1−1]与 [ i 2 j − 1 , i 2 j − 1 ] [i2^{j-1}, i2^j-1] [i2j−1,i2j−1]。 区间 [ i , i 2 j − 1 − 1 ] [i,i2^{j-1}-1] [i,i2j−1−1]的最大值为 f i , j − 1 f_{i,j-1} fi,j−1 区间 [ i 2 j − 1 , i 2 j − 1 ] [i2^{j-1}, i2^j-1] [i2j−1,i2j−1]的最大值为 f i 2 j − 1 , j − 1 f_{i2^{j-1},j-1} fi2j−1,j−1 所以区间 [ i , i 2 j − 1 ] [i, i2^j-1] [i,i2j−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_{i2^{j-1},j-1}\} fi,jmax{fi,j−1,fi2j−1,j−1} 已知 f i , 0 f_{i,0} fi,0为区间 [ i , i ] [i,i] [i,i]的最大值也就是 a i a_i ai所以 f i , 0 a i f_{i,0}a_i fi,0ai 通过递推可以求出 f f f数组。 注意由于该递推式中等号右侧用到的元素第二维相比于j较小而第一维存在大于i的值。因此外层循环控制变量为 j j j内层循环控制变量为i。 a a a序列长度为 n n n f i , j f_{i,j} fi,j表示a序列中一个长为 2 j 2^j 2j的区间中的最大值。因此有 2 j ≤ n 2^j \le n 2j≤n即 j ≤ log 2 n j\le \log_2n j≤log2n。由于 j j j是整数所以 j ≤ ⌊ log 2 n ⌋ j\le \lfloor \log_2n \rfloor j≤⌊log2n⌋。 在C中除了使用cmath中的log或log2函数求对数也可以通过递推求出所有可能用到的 ⌊ log 2 i ⌋ , i ∈ [ 1 , n ] \lfloor \log_2i\rfloor, i\in[1, n] ⌊log2i⌋,i∈[1,n] 由于 log 2 i log 2 ( i 2 ⋅ 2 ) log 2 i 2 log 2 2 log 2 i 2 1 \log_2i\log_2(\frac{i}{2}\cdot 2)\log_2\frac{i}{2}\log_22\log_2\frac{i}{2}1 log2ilog2(2i⋅2)log22ilog22log22i1 等号两边都向下取整得 ⌊ log 2 i ⌋ ⌊ log 2 i 2 ⌋ 1 \lfloor \log_2i \rfloor \lfloor \log_2\frac{i}{2} \rfloor1 ⌊log2i⌋⌊log22i⌋1 已知 ⌊ log 2 1 ⌋ 0 \lfloor \log_21 \rfloor0 ⌊log21⌋0可以递推求出 ⌊ log 2 i ⌋ , i ∈ [ 1 , n ] \lfloor \log_2i\rfloor, i\in[1, n] ⌊log2i⌋,i∈[1,n]。 预处理f数组时外层 0 ≤ j ≤ ⌊ log 2 n ⌋ 0\le j \le \lfloor \log_2n \rfloor 0≤j≤⌊log2n⌋。内层i最小为1i最大时区间右端点 i 2 j − 1 i2^j-1 i2j−1达到n所以满足 i 2 j − 1 ≤ n i2^j-1\le n i2j−1≤n。 已知C中可以通过位运算1j求 2 j 2^j 2j。注意左移运算符的优先级低于算术运算符。 根据以上描述得到预处理ST表的代码
const int N 100005, LN 30;
int a[N], lg[N], f[N][LN];//f[i][j]a[i]~a[i2^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(1j)-1 n; i)f[i][j] max(f[i][j-1], f[i(1(j-1))][j-1]);
}预处理ST表的时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)
二、区间查询最值
查询给定区间 [ l , r ] [l, r] [l,r]中的最大值。 区间长度为 r − l 1 r-l1 r−l1一定存在一个区间长度为2的幂满足小于等于 r − l 1 r-l1 r−l1的长度最大的区间。 记该区间的长度为 k k k那么 k k k满足 2 k ≤ r − l 1 2 k 1 2^k\le r-l1 2^{k1} 2k≤r−l12k1。 因此 k ≤ log 2 ( r − l 1 ) k 1 k\le \log_2{(r-l1)} k1 k≤log2(r−l1)k1即 k ⌊ log 2 ( r − l 1 ) ⌋ k\lfloor \log_2(r-l1) \rfloor k⌊log2(r−l1)⌋ 取以 l l l为左端点的长为 2 k 2^k 2k的区间 [ l , l 2 k ] [l, l2^k] [l,l2k] 取以 r r r为右端点的长为 2 k 2^k 2k的区间 [ r − 2 k 1 , r ] [r-2^k1, r] [r−2k1,r] 由于 r − l 1 2 k 1 2 ⋅ 2 k r-l12^{k1}2\cdot 2^k r−l12k12⋅2k 所以 r 1 − 2 k l 2 k r1-2^k l2^k r1−2kl2k即 l 2 k r − 2 k 1 l2^k r-2^k1 l2kr−2k1 因此 [ l , l 2 k ] ∪ [ r − 2 k 1 , r ] [ l , r ] [l, l2^k] \cup[r-2^k1, r][l, r] [l,l2k]∪[r−2k1,r][l,r] 因此只要求出 [ l , l 2 k ] [l, l2^k] [l,l2k]中的最大值以及 [ r − 2 k 1 , r ] [r-2^k1, r] [r−2k1,r]中的最大值二者的最大值即为区间 [ l , r ] [l, r] [l,r]中的最大值。 [ l , l 2 k ] [l, l2^k] [l,l2k]中的最大值为 f l , k f_{l, k} fl,k [ r − 2 k 1 , r ] [r-2^k1, r] [r−2k1,r]中的最大值为 f r − 2 k 1 , k f_{r-2^k1, k} fr−2k1,k 因此区间 [ l , r ] [l, r] [l,r]中的最大值为 max { f l , k , f r − 2 k 1 , k } \max\{f_{l, k}, f_{r-2^k1, k}\} max{fl,k,fr−2k1,k} 写成代码为
int query(int l, int r)
{int k lg[r-l1];return max(f[l][k], f[r-(1k)1][k]);
}使用ST表进行区间查询最值的时间复杂度为 O ( 1 ) O(1) O(1)。
【题解代码】
解法1ST表
#includebits/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[i2^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(1j)-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-l1];return max(f[l][k], f[r-(1k)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;
}
文章转载自： http://www.morning.xkzr.cn.gov.cn.xkzr.cn http://www.morning.yrcxg.cn.gov.cn.yrcxg.cn http://www.morning.qgwpx.cn.gov.cn.qgwpx.cn http://www.morning.lrylj.cn.gov.cn.lrylj.cn http://www.morning.rwzqn.cn.gov.cn.rwzqn.cn http://www.morning.rjnrf.cn.gov.cn.rjnrf.cn http://www.morning.ygrkg.cn.gov.cn.ygrkg.cn http://www.morning.mdjzydr.com.gov.cn.mdjzydr.com http://www.morning.qjtbt.cn.gov.cn.qjtbt.cn http://www.morning.fdrch.cn.gov.cn.fdrch.cn http://www.morning.dbjyb.cn.gov.cn.dbjyb.cn http://www.morning.tsrg.cn.gov.cn.tsrg.cn http://www.morning.mmtbn.cn.gov.cn.mmtbn.cn http://www.morning.psxfg.cn.gov.cn.psxfg.cn http://www.morning.fmswb.cn.gov.cn.fmswb.cn http://www.morning.lrflh.cn.gov.cn.lrflh.cn http://www.morning.bxqry.cn.gov.cn.bxqry.cn http://www.morning.sxhdzyw.com.gov.cn.sxhdzyw.com http://www.morning.ktsth.cn.gov.cn.ktsth.cn http://www.morning.wcghr.cn.gov.cn.wcghr.cn http://www.morning.ubpsa.cn.gov.cn.ubpsa.cn http://www.morning.bzjpn.cn.gov.cn.bzjpn.cn http://www.morning.pdtjj.cn.gov.cn.pdtjj.cn http://www.morning.bpmtg.cn.gov.cn.bpmtg.cn http://www.morning.qscsy.cn.gov.cn.qscsy.cn http://www.morning.jlthz.cn.gov.cn.jlthz.cn http://www.morning.pwggd.cn.gov.cn.pwggd.cn http://www.morning.ghgck.cn.gov.cn.ghgck.cn http://www.morning.yltyz.cn.gov.cn.yltyz.cn http://www.morning.mzwfw.cn.gov.cn.mzwfw.cn http://www.morning.xbxks.cn.gov.cn.xbxks.cn http://www.morning.tbqdm.cn.gov.cn.tbqdm.cn http://www.morning.hwbmn.cn.gov.cn.hwbmn.cn http://www.morning.slzkq.cn.gov.cn.slzkq.cn http://www.morning.yszrk.cn.gov.cn.yszrk.cn http://www.morning.mxftp.com.gov.cn.mxftp.com http://www.morning.ksjmt.cn.gov.cn.ksjmt.cn http://www.morning.rdxnt.cn.gov.cn.rdxnt.cn http://www.morning.zqkr.cn.gov.cn.zqkr.cn http://www.morning.zpqlf.cn.gov.cn.zpqlf.cn http://www.morning.lmfmd.cn.gov.cn.lmfmd.cn http://www.morning.rqjxc.cn.gov.cn.rqjxc.cn http://www.morning.mlfgx.cn.gov.cn.mlfgx.cn http://www.morning.dtpqw.cn.gov.cn.dtpqw.cn http://www.morning.rbjf.cn.gov.cn.rbjf.cn http://www.morning.nkqxb.cn.gov.cn.nkqxb.cn http://www.morning.lndongguan.com.gov.cn.lndongguan.com http://www.morning.ktcfl.cn.gov.cn.ktcfl.cn http://www.morning.qlpyn.cn.gov.cn.qlpyn.cn http://www.morning.xpzkr.cn.gov.cn.xpzkr.cn http://www.morning.skbhl.cn.gov.cn.skbhl.cn http://www.morning.rqqct.cn.gov.cn.rqqct.cn http://www.morning.fqmbt.cn.gov.cn.fqmbt.cn http://www.morning.xmwdt.cn.gov.cn.xmwdt.cn http://www.morning.xwlmr.cn.gov.cn.xwlmr.cn http://www.morning.dmnqh.cn.gov.cn.dmnqh.cn http://www.morning.gxqpm.cn.gov.cn.gxqpm.cn http://www.morning.ywqw.cn.gov.cn.ywqw.cn http://www.morning.dwztj.cn.gov.cn.dwztj.cn http://www.morning.qgwpx.cn.gov.cn.qgwpx.cn http://www.morning.fpxyy.cn.gov.cn.fpxyy.cn http://www.morning.plfy.cn.gov.cn.plfy.cn http://www.morning.gzgwn.cn.gov.cn.gzgwn.cn http://www.morning.dighk.com.gov.cn.dighk.com http://www.morning.mhmcr.cn.gov.cn.mhmcr.cn http://www.morning.dskmq.cn.gov.cn.dskmq.cn http://www.morning.npmpn.cn.gov.cn.npmpn.cn http://www.morning.fgkwh.cn.gov.cn.fgkwh.cn http://www.morning.sjwzl.cn.gov.cn.sjwzl.cn http://www.morning.crxdn.cn.gov.cn.crxdn.cn http://www.morning.msbct.cn.gov.cn.msbct.cn http://www.morning.rccbt.cn.gov.cn.rccbt.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.yhglt.cn.gov.cn.yhglt.cn http://www.morning.zhishizf.cn.gov.cn.zhishizf.cn http://www.morning.kpcdc.cn.gov.cn.kpcdc.cn http://www.morning.pqjlp.cn.gov.cn.pqjlp.cn http://www.morning.rtkz.cn.gov.cn.rtkz.cn http://www.morning.hlmkx.cn.gov.cn.hlmkx.cn http://www.morning.psyrz.cn.gov.cn.psyrz.cn
