0.前言好久没更算法笔记专栏了，正好学了新算法来更新……这也是本专栏的第一个专题问题，涉及到三种数据结构，如果写得有问题请各位大佬多多指教，谢谢！1.关于RMQ问题RMQ的全称是RangeMinimum/MaximumQuery，即区间最大/最小值问题。本文中，我们的算法以求最大值为例（最小值基本

还是rmq.原来如此代码：#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+7;inta[N],b[N],rmq[N][20];intpw(intk){intres=1;while(k--)res*=2;returnres;}intgetk(intl,intr){intk=0;while(r-l+1>=pw(k+1))++k;

倍增算法之：ST表与RMQ讲解：倍增思想，就是每次在原基础上往前“跳”\(2^n\)步RMQ参考https://blog.csdn.net/qq_31759205/article/details/75008659RMQ问题，即区间最值查询问题，通常的做法（我会的做法）有暴力、线段树……这里介绍一种比较高效的算法：ST表。ST表可以做到\(O(

ST表ST表，主要思想是空间换时间，用于解决可重复贡献问题和RMQ问题。可重复贡献问题指某个运算\(op\)，有\(x\op\x\=\x\)。例如\(max(x,x)=x\\min(x,x)=x\\gcd(x,x)=x\)。RMQ问题指在区间内的最大/最小值查询。ST表ST表基于倍增的思想，做到\(O(n\logn)\)

这貌似是一个很神奇的新科技。由乃救爷爷给你一个长为\(n\)的序列，你需要回答\(q\)次询问每次询问给出\(l,r\)，求\(\max\limits_{i=l}^ra_i\)。其中，\(n,m\le2\times10^7\)看起来好像是一个比较模板的RMQ，事实也确实如此。不过一般解决RMQ的方法都无法在正确的时间

#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;intf[100005][22];intmain(){intn,m;scanf("%d%d",&n,&m);for(inti=1;i<=n;i++)scanf("%d"

前天uq里有人问这个。单点修改区间\(min\)，能不能做到修改\(O(1)\)查询\(O(\sqrtn)\)。后来和@critno私下讨论了一会，得到了\(O(1)\)修改\(O(n^{\epsilon})\)查询的算法，并进行了简化版的实现。算法本质是操作序列分块。先考虑一个朴素算法。原序列不动，跑RMQ。

数据结构——RMQ（ST表）问题问题描述对于序列\(A[1\dotsn]\)，有\(m\)组询问\(\langlel,r\rangle\)，求\(\max_{i=l}^rA_i\)。我们下面使用\(\mathcalO(A)\sim\mathcalO(B)\)表示预处理\(\mathcalO(A)\)，单次询问\(\mathcalO(B)\)的时间复杂度。线段树解法时间复杂度

inta[50001];intf1[50001][20],f2[50001][20];inlinevoidwork1(){ for(inti=1;i<=n;i++) f1[i][0]=a[i]; for(intj=1;(1<<j)<=n;j++) for(inti=1;i+(1<<j)-1<=n;i++) f1[i][j]=max(f1[i][j-1],f1[

这是带上lazy标记的线段树板子inta[N];intls(intp){returnp<<1;}intrs(intp){returnp<<1|1;}classSegmentTree{public: inttree[N<<2|1],tag[N<<2|1]; inlinevoidpush_up(intp){ tree[p]=tree[ls(p)]+tree[rs(p)]; } in

RMQ问题：给定一个序列，并有一些询问，每次询问一个区间的最大值或最小值。下面以区间最大值为例进行讲解，设序列长度为\(N\)，有\(M\)次查询。1单调队列前提条件每个查询的区间互相不包含、离线、不能进行修改、不能在序列中增加元素。思路将所有查询按左端点排序（如果不保

P2048[NOI2010]超级钢琴前缀和处理连续子段的和弦，然后rmq求最大值运用堆存储最优答案每次取出堆头统计一次后，除掉统计点再分成两段加入即可，共k次#include<bits/stdc++.h>#definemaxn500010#defineINF0x3f3f3f3f#defineintlonglongusingnamespacestd;int

给出一个有n个数的序列，下标0~n-1，有Q次查询，每次询问区间[l,r]的最大值。如果有修改，可以考虑线段树，这里只有静态查询，可以用ST表，预处理时间O(nlogn)，单次查询时间O(1)。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definerep(i,a,b)for(inti=a;i<=b;i

这里会记一些不那么基础的RMQ算法，同时也会向外拓展到增量法规建笛卡尔树之类的东西。首先是基础的RMQ，静态可以用ST表做到\(O(n\logn)-O(1)\)，动态可以用线段树做到\(O(n)-O(\logn)\)，当然还有一些奇技淫巧可以用ST表维护特殊的动态RMQ。现在来看不基础的。询问区间定

区间最大最小值(RMQ)st表利用min,max区间合并是可重的，倍增预处理时间复杂度\(O(n\logn+q)\)空间复杂度\(O(n\logn)\)线段树二进制划分区间时间复杂度\(O(n\logn)\)methodoffourrussians建立笛卡尔树，求欧拉序，序列中相邻的两个元素绝对值为1，分块RMQ，状压，然后

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongchar*p1,*p2,buf[100000];#definenc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)intread(){intx=0,f=1;charch=nc();while(ch<48

主要应用倍增思想预处理：O(nlogn)查询：O(1)f[i][j]是以i为起点，长度为2j的区间中的最大值(一个点一个单位长度，不是一条线段)区间终点：i+2j-1<=n区间长度的指数k=log2(r-l+1)，只有当r-l+1为2n-1时是恰好分割，其他时候有重叠，但问题不大代码 #include<iostream>#include<cstring>#

题意是：给定一个长度为N的数列，和M次询问，求出每一次询问的区间内数字的最大值。ST表的基本功能是对区间进行查询，其核心使用的是倍增的思想f[i][k]:意思是从第i个数开始往后2^k个数f[i][k]=max(f[i][k-1],f[i+2^k-1][k-1])求【l,r】区间max(f[i][k],f[r-2^k+1][k])#define

题目描述给你一个序列\(a\)让你支持\(1\)\(l\)\(r\)\(x\)区间赋值\(2\)\(l\)\(r\)询问区间最小值我们觉得这个问题太水了,所以我们不会给你序列\(a\)而是给你序列一个长度为\(n\)的序列\(b\),把\(b\)复制粘贴\(k\)次就可以得到\(a\)\(n\le10^5,k\le10^4,q\le10

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;constintN=200010,M=18;intn,m;intw[N];intlg[N];intf[N][M];//查询区间最值//预处理f数组voidinit(){ lg[1]=0; for(inti=2;i&l

学习时间：2023/10/15CSP-S2023倒计时5days我竟然才会ST表简述ST表主要用于解决静态RMQ问题。实际上，凡是具备可重复贡献和结合律的问题，都可以用ST表来解决。ST表的优化方式和前缀和差分类似，采取预处理，每次可以做到\(O(1)\)时间复杂度的查询。因此，它适用于有大量查

P3865【模板】ST表利用倍增f[i][j]表示，范围[i,i+2^(j)-1]内的最大值是多少点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intf[N][22];intmain(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); intn,m; cin>>n>>

期望\(O(n)-O(1)的RMQ\)#include<bits/stdc++.h>#defineintlonglong#defineF(i0,i1,i2)for(inti0=(i1);i0<=(i2);++i0)usingnamespacestd;inlineintrd(){ intx=0,f=0;charch=getchar(); while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar(

目录RMQ问题ST表优缺点实现递推查询复杂度代码技巧-快速读入RMQ问题RMQ（RangeMaximum/MinimumQuery）问题，即区间最值问题。一般是多次询问，对时间复杂度要求高，一般需要\(O(logn)\)或\(O(1)\)复杂度ST表p[i][j]是以i为起点，连续\(2^j\)个数字的最大值(是一个递推表)3

Lnk。这是一个dfs序+主席树的乱搞做法。首先把树上距离拆开，令\(\operatorname{dis}(u)\)表示\(u\)到根的路径长度：\[\left(\sum_{i=l}^r\operatorname{dis}(p_i)\right)+\left(\sum_{i=l}^r\operatorname{dis}(x)\right)-2\sum_{i=l}^r\operatorname{dis}(\operatorna