分为三类吧
线段树
这种数据结构挺有用的，使用范围是时间，看着办嘛，\(O(n\log n)\)的算法，修改加入查询都是\(O(\log n)\)
然后建树\(O(n\log n)\)
看着办
大概思路就是将一个节点看做是一段区间，然后左子右子继承各区间的一半这样
实现还有各种创新
这种合并左右壁的
空间：4N
时间：如上
树状数组
首先知道lowbit函数
就是\(lowbit(x)=x\space and(x\bigoplus(x-1))\)
然后加入就是影响到后面的，所以就是
while(k<=n){
f[k]+=delta;
k+=lowbit(k);
}
然后求呢，树状数组不能求区间最大值，因为它一次只能求1-n的值
求的话，就是看前面的了
while(k>0){
sum+=f[k];
k-=lowbit(k);
}
然后时间与线段树一样
空间是N
但别看它码量少，它的功能不如线段树
前缀和
这个。。。
打个标题就算了
水沝㴇淼㵘爆了
倍增
一大利器
以\(f_{i}\)的形式存着，表示着\(2^i\)的意义，
方便转移，因为\(f_{i-1}\)
就是它的二分之一范围
应用之一：ST表
求区间最大值的，离线算法
有数\(a_{1...n}\)
设\(ST_{i,j}\)
为\(\max(a_{j...j+2^i-1})\)
然后转移就是枚举i,j，然后\(ST_{i,j}=\max(ST_{i-1,j},ST_{i-1,j+2^{i-1}})\)
也挺好想的哈
当然，初值就是\(ST_{0,i}=a_i\)
最后求答案
因为倍增的区间不一定能刚好覆盖l-r这个区间，嗯，其实也行，因为是倍增嘛，可以用倍增大片大片地跳
但这里再给出一个方法
就是找到起始位为l，能覆盖l-r区间左边一半的区间，然后再找到末尾为r，能覆盖l-r区间右半边的区间，然后求着两个区间的最大值就是整个区间的最大值了
这里给出代码
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,a[100001];
int f[21][100001];
int l,r,s,len;
int max(int x,int y){
return x>y?x:y;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[0][i]=a[i];
}
int l=log2(n),p=1;
for(int i=1;i<=l;i++){
for(int j=1;j+2*p-1<=n;j++){
f[i][j]=max(f[i-1][j],f[i-1][j+p]);
// printf("%d ",f[i][j]);
}
// printf("\n");
p*=2;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&l,&r);
s=log2(r-l+1);
len=pow(2,s);
printf("%d\n",max(f[s][l],f[s][r-len+1]));
}
}
应用之二：树套树、二维树状数组
这两个，就是求区间\(f_{l1...r1,l2...r2}\)的值了啊
套起来用就行
树状数组直接二重循环
线段树就是先找一维，再找另一维，分开两个函数大比较轻松，当然，一个函数中，分成四份向下查找那也行
总结
这便是RMQ了啊，比起谈论，更重要的是注意细节
嗯，当然，还有运用
标签：11,...,RMQ,树状,int,12th,然后,ST,区间 From： https://www.cnblogs.com/tlz-place/p/16724031.html