pigeonw blog
【算法】倍增
发布于: 2025-10-15 更新于: 2025-10-19 分类于:  阅读次数: 

定义

倍增法，顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。
这个方法在很多算法中均有应用，其中最常用的是 RMQ (Ranged Max/Min Query) 问题和求
LCA(Lowest Common Ancestor)。

引例

在你面前的桌子上，摆着无数个重量为任意整数的胡萝卜；
接着告诉你一个数字n，问你要怎么挑选，使得你选出的胡萝卜能够表示出 [1,n] 区间内的所有整数重量？

读完题后我们马上就能想到一种选法，那就是选n个重量为1的胡萝卜，这样就能通过加减表示出 [1,n] 内的所有重量了。

但问题是……这样挑选的胡萝卜是不是太多了点？

我们很快就能发现，只需要选择重量为 1,2,4,8 的胡萝卜，就能表示 [1,31] 内的所有重量。所以，只需要选择重量 2^0,2^1,2^2……2^n 的胡萝卜，就能表示 [1,n] 内的所有重量。

也就是说， 对于给定的数字 ，根本不需要选那么多胡萝卜，只需要 个胡萝卜就够啦！

由此引例我们得出一个结论：只需要的预处理，就能表示出 区间内的所有情况。

小结

这是一种 用二进制思想加速跳跃或转移 的算法技巧。
它的核心思想是：

如果我们能快速知道「走 2^k 步」后到哪里，
那么我们也能快速知道「走任意 x 步」后到哪里。

但是我们该如何递进呢？

应用 – ST表

问题

现在给你一个序列 a，要求每次查询在 O(1) 时间内求出某个区间的最大最小值

模板代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
ST图 模板
此模板以（洛谷）P2880 [USACO07JAN] Balanced Lineup G 为标准
通用大部分ST图的题 
*/ 
#include <iostream> 
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long

const int maxn=1e5+10; //此处可以修改 
const int lg_maxn=__lg(maxn)+10;

int a[maxn];
int f1[maxn][lg_maxn]; //max
int f2[maxn][lg_maxn]; //min

void init() //计算 
{
    for (int i=1;i<=n;i++) f1[i][0]=f2[i][0]=a[i];
    int k=log(n)/log(2);
    for (int j=1;j<=k;j++)
    {
        for (int i=1;i<=n-(1<<j)+1;i++)
        {
            f1[i][j]=max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]); //此处可以修改 
            f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]); //此处可以修改 
        }
    } 
}

int query(int l,int r) //查找 
{
    int p=log(r-l+1)/log(2);
    return max(f1[l][p],f1[r-(1<<p)+1][p])-min(f2[l][p],f2[r-(1<<p)+1][p]); //此处可以修改 
}

signed main()
{
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i];
    init();
    for (int i=1;i<=m;i++) 
    {
        int l,r;
        cin >> l >> r;
        cout << query(l,r) << endl;
    }
    return 0;
}

练习题

  1. P3865 【模板】ST 表
  2. P1816 忠诚
  3. P1890 gcd区间
  4. P2880 [USACO07JAN] Balanced Lineup G
  5. P2471 [SCOI2007] 降雨量

应用 – LCA 最近公共祖先

问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n,x,q; cin >> n >> x >> q;
    vector<int> a(n+1,0),b(n+1,0);
    for (int i=1;i<=n;i++) cin >> a[i] >> b[i];

    vector<vector<int>> dp(n+1,vector<int>(1010,1e15));

    dp[0][0]=0;
    for (int i=1;i<=n;i++) {
        for (int j=0;j<dp[i-1].size();j++) {
            if (dp[i-1][j]==1e15) continue;
            dp[i][j]=min(dp[i][j],dp[i-1][j]);
            for (int k=1;k<=b[i];k++) {
                int nj=j+k+(k==b[i]?1:0);
                dp[i][nj]=min(dp[i][nj],dp[i-1][j]+k*a[i]);
            }
        }
    }
    
    int ans=1e15;
    for (int j=x;j<dp[n].size();j++) {
        if (dp[n][j]==1e15) continue;
        ans=min(ans,dp[n][j]+(j-x)*q);
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
--- 本文结束 The End ---