经典算法和数据结构

2026-03-05

数据结构算法 Cpp

ST表和倍增算法

1.ST表

ST表通常用于解决区间可重复贡献问题（区间最值）

考虑这样的问题：

给定一个长度为$n$ 的数组，$q$次询问，每次询问要求查询$[l,r]$范围的数组元素最大值

基于ST表进行$O(nlogn)$预处理，$O(1)$查询

令$f[i][j]$表示区间$[i,i+2^j-1]$的最大值

区间$[l,r]$的长度为$r-l+1$,令$k=log_2(r-l+1)$

那么$ans = max(f[l][k],f[r-2^k+1][k])$

预处理过程如下：

int f[M][32];
int a[M];
int Log[M];
int n;
void build(){
    Log[1]=0;
    for(int i=2;i<=n;i++){
        Log[i]=Log[i/2]+1;
    }
    for(int i=1;i<=n;i++)f[i][0]=a[i];
    for(int j=1;j<=31;j++){
        for(int i=1;i<=n&&(i+(1ll<<j-1))<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1ll<<j-1)][j-1]);
        }
    }
}

询问

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

除RMQ以外，ST表还可以处理区间按位与，按位或，区间GCD等问题

但是，ST 表能维护的信息非常有限，不能较好地扩展，并且不支持修改操作

2.倍增

基于二进制的划分思想

考虑这样的问题：

给定一个单调不减序列，多次查询，每次查询给定一个数，求该数在序列中第一次出现的位置。

可以二分答案，但也可以使用倍增

int x;cin>>x;
int p=0,step=1;
while(step){
	if(p+step<=n&&a[p+step]<x){
		p=p+step;
		step<<=1;
	}else{
		step>>=1;
	}
}
if(p<n&&a[p+1]==x){
	cout<<p+1<<' ';
}else{
	cout<<-1<<' ';
}

像这样先翻倍增长步长，再翻倍减少步长是倍增的实现方式之一

快速幂

$O(logn)$求$a^b$同样运用到了倍增

int ksm(int a,int b){
	int ans = 1;
	while(b){
		if(b&1)ans=ans%mod*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}

求LCA

倍增法求一颗树上的两个结点的LCA

预处理$dep$数组和$f[i][0]$（$i$结点的父节点编号）
预处理出整个$f$数组
对于查询结点$u$和$v$，先让两个结点跳到同一深度，再向上判断$LCA$

int n,m,s;
vector<int>e[M];
int f[M][32];
int dep[M];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int v:e[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
}
int find(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int j=31;j>=0;j--){
        if(dep[f[u][j]]>=dep[v]){
            u=f[u][j];
        }
        if(u==v)return u;
    }
    for(int j=31;j>=0;j--){
        if(f[u][j]!=f[v][j]){
            u=f[u][j];v=f[v][j];
        }
    }
    return f[u][0];
}
void solve(){
    cin>>n>>m>>s;
    for(int i=1;i<=n-1;i++){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dep[0]=-1;
    dfs(s,0);
    for(int i=1;i<=31;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        cout<<find(u,v)<<endl;
    }
}