倍增

  • 倍增是一种思想，也是一个算法
  • 倍增比二分的常数要大，但比二分更好写 
int x=-1;
for(int i=31;~i;--i) if(pan(x+(1<<i)) x+=(1<<i);      // ~i的意思是i!=-1
  • 倍增在树上和链上更常见

ST表

跳表用于只需查询的问题中【把需要的信息预处理】
ST表又叫跳表
ST表有两种，一种是根号跳表，另一种是倍增跳表
跳表是为了处理静态查询问题，线段树既可以处理静态查询，也可以处理动态查询

区间长度为n【1e5的话】，查询m次
跳表相对于线段树的优势在于，其单次查询是O(1)的，线段树的查询是O（lgn)的【线段树查询可能跑不满 lg】
而相对而言，其预处理是O(nlgn)【lg跑满了】,线段树建树也是O(nlgn)【lg跑不满】
所以跳表在查询次数非常大时，才能发挥优势，否则直接上线段树吧
所以m<=n时，跳表不具优势，但 m=10N 时，倍增跳表时间优，m=100N 时，根号跳表时间更优【根号跳表比倍增跳表需要的空间要大】

st表的本质：st[i][j]表示以i为起点，长度为 j 的区间信息，其本质就是预处理区间信息（不需要后期维护）

根号跳表 

根号跳表原理： 
n可以分解为sqrt(n)*sqrt(n) 
任何一个数x都可以写成 a*sqrt(n)+b  //a小于sqrt(n),b也小于sqrt(n) 

st_small[N][sqrt(N)]; //小表，st_sm[i][j]表示以i为起点，长度为j的区间最值   // j<=sqrt(n)
st_big[N][sqrt(N)]; //大表，st_big[i][j]表示以i为起点，长度为j*sqrt(n)的区间最值  //j<=sqrt(n)

int z=sqrt(n);
st_sm[i][1]=a[i];
st_sm[i][j]=max(st_sm[i][j-1],a[i+j-1]);

st_big[i][1]=st_sm[i][z];
st_big[i][j]=max(st_big[i][j-1],st_sm[i+(j-1)*z][z]);

int ask(int l,int r){
	int len=r-l+1;
	return max(st_big[l][len/z],st_sm[l+len/z*z][len-(len/z*z)]);   //也可以写成%，但为了好理解，写成减比较好 
}

#include<bits/stdc++.h>
using namespace std;
int const N=1e5+7;
int const L=3e2+7;
int n,m,bl;
int a[N];
int sts[N][L],stb[N][L];
int ask(int l,int r){
	int len=r-l+1;
	return max(stb[l][len/bl],sts[l+len/bl*bl][len-len/bl*bl]);  //
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;++i) cin >> a[i];
	bl=ceil(sqrt(n));
	for(int i=1;i<=n;++i){
		for(int j=1;j<=bl&&i+j-1<=n;++j){  //&&i+j-1<=n 为实际意义的限制，既可以防止数组越界，又可以优化时间常数  //以后这种情况都这么写（for有好几个限制时，把条件全部写出来），这么写不会错，不写还要考虑是否越界，还会增大时间常数
			if(j==1) sts[i][j]=a[i];
			else sts[i][j]=max(sts[i][j-1],a[i+j-1]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=bl&&i+j*bl-1<=n;++j){   //&&i+j*bl-1<=n   //j<=bl可以省略
			if(j==1) stb[i][j]=sts[i][bl];
			else stb[i][j]=max(stb[i][j-1],sts[i+(j-1)*bl][bl]);   //
		}
	}	
	int l,r;
	while(m--){
		cin >> l >> r;
		cout << ask(l,r) << "\n";
	}
	return 0;
}

倍增跳表

用于查询可重复合并的区间信息，比如 RMQ，GCD等等，也就是多次合并不影响结果 
倍增跳表原理：
st[N][lg(N)];    //st[i][j]表示以i为起点，长度为2^j的区间最值

st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

int ask(int l,int r){
    int k=log2(r-l+1);   //向下取整
    return max(st[l][k],st[r-(1<<k)][k]);
}

log2不要调用系统函数
众所周知，在处理整数问题上，pow,log,log2,sqrt等函数都比较有问题
第一是精度问题【它们是先转换成小数运算，再转换回整数】，第二是时间常数

预处理log2
如果范围不大，可以暴力预处理
LG2[1]=0;
for(int i=2;i<n;++i) LG2[i]=LG2[i/2]+1;   //因为对数【logx(y)】的实际意义就是y能除以x几次，与幂的定义【运算】相反，幂【x^y】是x乘y次的结果

扩展：
LGX[1]=0;
for(int i=2;i<n;++i) LGX[i]=LGX[y/x]+1;



#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define ll long long
int const N=1e5+7;
int n,m;
int a[N];
int st[N][20];
void build(){
	for(int i=1;i<=n;++i) st[i][0]=a[i];
	for(int j=1;(1<<j)<=n;++j){
		for(int i=1;i<=n&&i+(1<<j)-1<=n;++i){  //i<=n可以省略 
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
int LG2[N];
void init(){
	LG2[1]=0;
	for(int i=2;i<=n;++i) LG2[i]=LG2[i/2]+1;   //这里的LG2是lg2向下取整 
}
int ask(int l,int r){
	int len=r-l+1;
	int k=LG2[len];
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
	fio;
	cin >> n >> m;
	for(int i=1;i<=n;++i) cin >> a[i];
	build();
	init();
	int l,r;
	while(m--){
		cin >> l >> r;
		cout << ask(l,r) << "\n";
	}
	return 0;
}