本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，~~主要是因为我三本都买了~~ 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的部分重要知识点、例题答案及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（~~习题和代码可全都是我自己敲哒~~）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》— 作者李煜东，强烈安利，好书不火系列，谢谢配合。

下方链接为学习笔记目录链接（中转站）

今天到了倍增，倍增算法之前学习过一些，写过一些入门的博客，建议可以看一下：倍增算法入门超详细解答+LCA+RMQ(ST表)+例题剖析，~~其实跟今天的这个博客内容重复挺大的。~~ 因为倍增本就是一个比较基础的算法。把我之前的博客看完就可以把下面的看一遍复习一下了

一、倍增

倍增, 从字面的上意思看就是成倍的增长 ,这是指我们在进行递推时,如果状态空间很大,通常的线性递推无法满足时间和空间复杂度的要求 ,那么我们就可以通过成倍的增长,只递推状态空间中在 2 的整数次幂位置上的值作为代表。当需要其他位置上的值时,我们只需要通过" 任意整数可以表示成若干个2的次幂项的和 " 这一性质( $13 = 2^{3} + 2^{2} + 2^{0}$ ), 使用之前求出的代表值拼成所需的值。

0.例题引入

给定一个长度为 N 的数列 A ,然后进行若干次查询 , 每一次给定一个整数 T , 求出最大的 k , 满足 $\sum_{1 = 1}^{k} A [i] < = T$ . 算法必须是在线的(每给一次询问,就给出结果) ;

我们可以设计这样一个倍增算法 :

1 . 令 $p = 1, k = 0, s u m = 0$ ;

2 . 比较" A 数组中 k 之后的 p 个数的和" 与 T 的关系 , 也就是说 ,如果 $s u m + s [k + p] - s [k] < = T$ , 则令 $s u m + = s [k + p] - s [k], k + = p, p * = 2;$ 也就是累加上这 p 个数的和 ,然后把 p 的跨度增长了一倍。如果 $s u m + s [k + p] - s [k] > T$ , 则令 $p / = 2$ .

3 重复上一步,直到 p 的值变为0 , 此时 k 就是答案 .

如果看完我的倍增入门的博客，那么上面的这个方法很显然就是直接利用倍增思想，就像博客里的那一只聪明跑路的小白兔那样。

应该很好理解

注意这里我加了一个特判是因为如果p经过神奇的运算会小于k，那么代码就会直接死循环，不信你把那个特判删了然后试试我编的这组数据：
输入：

5
1 2 3 4 5
10

输出：

然后就是代码了（注意这里只是简单的应用帮助理解倍增，并不一定是本题的正确解法）

#include<iostream>
#include<string.h>
#include<cstdio>
#include<math.h>
#include<map>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const ll N=100001;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0

ll n,m,a[N],sum[N];
ll T;
int main()
{
    cin>>n;
    over(i,1,n)
        scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
    ll k=0,p=1,s=0;
    cin>>T;
    while(p!=0){   
        //神奇的特判
        if(s+sum[k+p]-sum[k]<=T&&sum[k+p]-sum[k]>0){
            s+=sum[k+p]-sum[k];
            k+=p;p*=2;
        }
        else p/=2;
    }
    printf("%lld\n",k);
    return 0;
}

1.AcWing 109.Genius ACM（归并+倍增）

https://www.acwing.com/problem/content/111/
题目描述
给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下:
从集合 S 中取出 M 对数(即 2∗M 个数，不能重复使用集合中的数，如果 S 中的整数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 S 的“校验值”。
现在给定一个长度为 N 的数列 A 以及一个整数 T。
我们要把 A 分成若干段，使得每一段的“校验值”都不超过 T。
求最少需要分成几段。
输入格式
第一行输入整数 K，代表有 K 组测试数据。
对于每组测试数据，第一行包含三个整数 N,M,T。
第二行包含 N 个整数，表示数列A1,A2…AN。
输出格式
对于每组测试数据，输出其答案，每个答案占一行。
数据范围
$1 \leq K \leq 12$
$1 \leq N, M \leq 500000$
$0 \leq T \leq 1018$
$0 \leq A$
输入样例：

输出样例：

2
1

https://www.acwing.com/solution/acwing/content/894/

二、ST算法

RMQ问题中，著名的ST算法就是倍增的产物，给定一个长度为N的数列A，ST算法能够在 $O (N \log N)$ 的预处理之后，以 $O (1)$ 的时间复杂度在线回答区间最值的询问。

一个序列的子区间个数显然有 $O (N^{2})$ 个，根据倍增思想，我们首先在这个规模为 $O (N^{2})$ 的状态空间内选择一些2的整数次幂的位置作为代表值。

设 $F [i, j]$ 代表数列A中下标在区间 $[i, i + 2^{j} - 1]$ 里的数的最大值，也就是从i开始的 $2^{j}$ 个数的最大值，递推边界显然是 $F [i, 0] = A [i]$ 。

在递推时，我们把子区间的长度成倍增长，有公式 $F [i, j] = m a x (F [i, j - 1], F [i + 2^{j - 1}, j - 1])$ ，即长度为 $2^{j}$ 的子区间的最大值是左右两半长度为 $2^{j - 1}$ 的子区间的最大值中较大的一个。

void ST_prework()
{
    for (int i = 1; i <= n; ++i) f[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; ++j)
    {
        for (int i = 1; i <= n - (1 << j) + 1; ++i)
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

当询问任意区间 $[l, r]$ 的最值时，我们先计算出一个k，满足 $2^{k} < = r - l + 1 < = 2^{k + 1}$ ，那么以l开头的 $2^{k} 2$ 个数和以r结尾的 $2^{k}$ 个数一定覆盖了整个区间 $[l, r]$ ，而且这两段的最大值分别是 $F [l, k]$ 和 $F [r - 2^{k} + 1, r]$ ，因为是求最大值，所以即使有重合也没有关系。

int ST_query(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

简便起见，代码中使用了 $l o g$ 函数，该函数效率较高，一般来说对程序性能影响不大。更严格来讲，为了保证复杂度为 $O (1$ )，应该预处理出1 ~ N这N种区间长度各自对应的k值，在询问时直接使用。

2.luogu P3865 【模板】ST表

P3865 【模板】ST表

完整代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>

#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)

using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=500007;
const ll INF=1e9+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,f[N][21],a[N];

inline void ST()
{
    over(i,1,n)
        f[i][0]=a[i];//初始化,以自己为起点2^0=1长的区间就是他自己
    for(ll j=1;(1<<j)<=n;++j)//枚举区间长度
        for(ll i=1;i+(1<<j)-1<=n;++i)//枚举起点
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//取最大值
}

inline ll query(ll l,ll r)
{
    ll k=trunc(log2(r-l+1));
    return max(f[l][k],f[r-(1<<k)+1][k]);//因为已经用区间DP初始化过了，所以直接比较输出即可
}

int main()
{
    scanf("%lld%lld",&n,&m);
    over(i,1,n)scanf("%lld",&a[i]);
    ST();
    over(i,1,m)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        printf("%lld\n",query(x,y));
    }
    return 0;
}

三、求LCA（Least Common Ancestors），最近公共祖先

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。
———来自百度百科

还是不懂的话建议再看这个博客：https://blog.csdn.net/weixin_45697774/article/details/105289810

这里再简单地说一下思路：

先dfs预处理好深度，把父节点和 $2^{i}$ 级的祖先存到数组里，init一个lg数组优化，然后开始从大到小利用倍增往上爬，爬到父节点的子节点，输出父节点。

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧

0x06.基本算法—倍增