【算法竞赛学习笔记】倍增法

title : 倍增法
date : 2022-3-15
tags : ACM,杂项，算法基础
author : Linno

倍增法(binary lifting)，是一种每次将情况翻倍从而将线性处理转化为对数级处理，进而极大优化时间复杂度的方法。

对于区间 [ i , i + 2 k ] [i,i+2^k] [i,i+2k]求最大/最小值，实际上就是对前 [ i , i + 2 k − 1 ] [i,i+2^{k-1}] [i,i+2k−1]和 [ i + 2 k − 1 + 1 , 2 k ] [i+2^{k-1}+1,2^k] [i+2k−1+1,2k]两个区间求最大/最小值。如果我们预处理出每个数字 i i i加上 2 p 2^p 2p次幂范围的答案，那么就可以 O ( 1 ) O(1) O(1)得到 [ i , i + 2 p + 1 ] [i,i+2^{p+1}] [i,i+2p+1]区间的结果。阈值是 O ( n l o g n ) O(nlogn) O(nlogn)的预处理。

//luoguP3865 【模板】ST 表
#include
using namespace std;
typedef long long ll;

ll n,m,l,r,lg2[32],fang[32],a[1000005][32];

int main(){
	scanf("%lld%lld",&n,&m);
	lg2[0]=-1;for(int i=1;i<=31;i++) lg2[i]=lg2[i/2]+1;
	fang[0]=1;for(int i=1;i<=31;i++) fang[i]=fang[i-1]*2;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int j=1;j<=31;j++){
		for(int i=1;i+fang[j]-1<=n;i++){
			a[i][j]=max(a[i][j-1],a[i+fang[j-1]][j-1]);
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&l,&r);
		int len=log2(r-l+1);
		ll ans=max(a[l][len],a[r-fang[len]+1][len]);
		printf("%lldn",ans);
	}
	return 0;
}

我们设某一点的第 k k k级父亲就是向上跳 2 k 2^k 2k次所到达的结点，那么对于两点求最近公共祖先就可以用 O ( l o g n ) O(logn) O(logn)来解决。

//luoguP3379 【模板】最近公共祖先（LCA）
#include
#include
#include
using namespace std;
const int maxn=500005;
int n,m,rt;
int d[maxn],f[maxn][22];
int lg[maxn];
vectorG[maxn];

void dfs(int u,int fa){
	d[u]=d[fa]+1;
	f[u][0]=fa;
	//f[u][0]是父亲，然后是第二个祖先，第四个祖先，。。。以此类推 
	for(int i=0;id[y]) x = f[x][lg[d[x]-d[y]]-1]; 
	for(int i=20;i>=0;i--) if(d[f[x][i]]>=d[y]) x=f[x][i];
	if(x == y) return x;               //此时深度相同。两者相等的话说明原先的y是x的祖先。此时的x或y就是lca
	//倍增【2】：找lca。【二进制思维】从大到小尝试往上跳 
	//如果两者祖先不相等就往上跳：x跳到第2^【log2(x的深度)-1】（即：x的深度-1）个祖先 
	//鉴于x和y的深度一直一样，因此如果祖先相等，说明可能超过了lca的位置。
	for(int k = lg[d[x]]-1;k>=0;--k)           
		if(f[x][k]!=f[y][k]) x = f[x][k],y = f[y][k]; 
	return f[x][0];                   
}

void init(int n){
	memset(d,0,sizeof(d));
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;++i) G[i].clear();
} 

int main(){
	//int t;
	//scanf("%d",&t);
	scanf("%d%d%d",&n,&m,&rt);
	for(int i=1;i<=n;++i) lg[i] = lg[i-1] + (1< 
P1081 [NOIP2012 提高组] 开车旅行 
我认为这是一道好题。可利用倍增去优化DP，思路非常灵活。
 
这是洛谷题解置顶的代码，码量我感觉还是比较大的，但是写得很好看，就拿来用了。
 
#include
using namespace std;
const int N=1e5+200,INF=2e9;
struct City{
    int id,al;
    friend bool operator < (City a,City b){
        return a.alq; //用于存下一个目标城市 

void calc(int S,int X){
    int p=S;
    la=0,lb=0;
    for(int i=18;i>=0;i--)
        if(f[i][p][0] && la+lb+da[i][p][0]+db[i][p][0]<=X)
        {
            la+=da[i][p][0];
            lb+=db[i][p][0];
            p=f[i][p][0];
        }
}

void pre(){ //2、预处理 
    h[0]=INF,h[n+1]=-INF; 
    q.insert({0,INF}),q.insert({0,INF}); 
    q.insert({n+1,-INF}),q.insert({n+1,-INF});
    for(int i=n;i;i--){ //使用集合找到两个最近的前驱和后继 
        int ga,gb;
        City now;
        now.id=i,now.al=h[i];
        q.insert(now);
        set::iterator p=q.lower_bound(now);
        p--;
        int lt=(*p).id,lh=(*p).al;//last
        p++,p++;
        int ne=(*p).id,nh=(*p).al;//next
        p--;
        if(abs(nh-h[i])>=abs(h[i]-lh)){
            gb=lt;
            p--,p--;
            if(abs(nh-h[i])>=abs(h[i]-(*p).al)) ga=(*p).id;
            else ga=ne;
        }else{
            gb=ne;
            p++,p++;
            if(abs((*p).al-h[i])>=abs(h[i]-lh)) ga=lt;
            else ga=(*p).id;
        }
        f[0][i][0]=ga,f[0][i][1]=gb;
        da[0][i][0]=abs(h[i]-h[ga]);
        db[0][i][1]=abs(h[i]-h[gb]);//3、DP初值
    }
    for(int i=1;i<=18;i++)  //dp转移过程 
        for(int j=1;j<=n;j++)
            for(int k=0;k<2;k++)
                if(i==1){
                    f[1][j][k]=f[0][f[0][j][k]][1-k];
                    da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];
                    db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][1-k]; 
                }else{
                    f[i][j][k]=f[i-1][f[i-1][j][k]][k];
                    da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];
                    db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];
                }//3、倍增优化DP
}

void input(){ //数据读入 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    cin>>x0>>m;
    for(int i=1;i<=m;i++) cin>>s[i]>>x[i];
}

signed main(){
	input();
    pre();
    for(int i=1;i<=n;i++){ //4、求解问题1
        calc(i,x0);
        double nowans=(double)la/(double)lb;
        if(nowans 
参考文献 
https://oi-wiki.org/basic/binary-lifting/
 
https://www.cnblogs.com/YangKun-/p/12524015.html
 
https://blog.csdn.net/jarjingx/article/details/8180560
 
https://www.luogu.com.cn/blog/TEoS/p1081-kai-ju-lv-xing