一、倍增算法
要了解倍增之前，强烈建议大家先看一下这位大佬对倍增的解释：【白话系列】倍增算法
看完以后相信你已经对倍增有了大致初步的了解，下面给出倍增的定义
倍增 从字面的上意思看就是成倍的增长 ,这是指我们在进行递推时,如果状态空间很大,通常的线性递推无法满足时间和空间复杂度的要求 ,那么我们就可以通过成倍的增长,只递推状态空间中在 2 的整数次幂位置上的值作为代表 。当需要其他位置上的值时,我们只需要通过" 任意整数可以表示成若干个2的次幂项的和 " 这一性质( 13=23+22+20 ), 使用之前求出的代表值拼成所需的值。
给定一个长度为 N 的数列 A ,然后进行若干次查询 , 每一次给定一个整数 T , 求出最大的 k , 满足 ∑1=1kA[i]<=T . 算法必须是在线的(每给一次询问,就给出结果) ;
我们当然可以先 预处理前缀和 , ( A[i]>0 )然后用 二分找到 这个k , 这个复杂度最坏是 O(n) , 因为如果我们的 询问的T 太小 ,就还不如从前往后枚举。
我们可以设计这样一个 倍增算法 :
1 . 令 p = 1 , k = 0 , sum = 0 ;
2 . 比较" A 数组中 k 之后的 p 个数的 和" 与 T 的关系 , 也就是说 ,如果 sum+s[k+p]−s[k]<=T , 则令 sum+=s[k+p]−s[k],k+=p,p∗=2; 也就是累加上这 p 个数的和 ,然后把 p 的跨度增长了一倍。如果 sum+s[k+p]−s[k]>T , 则令 p/=2 .
3 重复上一步,直到 p 的值变为0 , 此时 k 就是 答案 .
注意这里我加了一个特判是因为如果p经过神奇的运算会小于k，那么代码就会直接死循环，不信你把那个特判删了然后试试我编的这组数据：
输入：
5
1 2 3 4 5
10
输出：
4
然后就是代码了（注意这里只是简单的应用帮助理解倍增，并不一定是本题的正确解法）
#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;
}
利用的就是任意整数可以表示成若干个2 的 次幂项的和 ，还有一个应用就是DP的多重背包，利用二进制拆分把完全背包或者多个背包全部拆成01背包直接按照01背包来做。感兴趣的话可以看看我写的这个博客
接下来就是倍增算法最常(jian)见(dan)的两种应用，RMQ（区间最值查询）和LCA（最近公共祖先）
二、倍增算法的应用：求LCA（最近公共祖先）附模板题
LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科
比如这一颗二叉树，D和E的LCA很明显是根A，要注意的是D和B的LCA应该是B它本身。
先看一下模板题
要找两个节点的LCA，暴力走的话就一步一步地往上爬，当然时间复杂度会贼高，不可取，你会发现一步一步往上爬就跟开篇我分享的那一篇博客里写的小兔子往前走一模一样，所以同样可以用倍增算法来优化。
就是按2的倍数来增大，也就是跳 1,2,4,8,16,32…… 不过在这我们不是按从小到大跳，而是从大向小跳，即按 ……32,16,8,4,2,1来跳，如果大的跳不过去，再把它调小。这是因为从小开始跳，可能会出现“悔棋”的现象。拿 5 为例，从小向大跳， 5=1+2+4,所以我们还要回溯一步，然后才能得出 5=1+4；而从大向小跳，直接可以得出 5=4+1。这也可以拿二进制为例， 5(101)，从高位向低位填很简单，如果填了这位之后比原数大了，那就不填了，这个过程是很好操作的。
所以整体思路就是用倍增算法来优化往上跳的时间，先用一个dfs预处理一下树，把所有节点的深度，父节点和它的 2i级的祖先全部用数组存起来，方便直接跳
其中几个重要的数组：
- depth数组是记录每个节点的深度
- fa[i][j]是指节点 i 的 2j 级的祖先的编号
- head数组是链式前向星的数组
相信大家都会，这里就不展开了 - lg数组是常数优化的数组，存的是log2N+1的值，注意用的时候要-1，开始之前先初始化一下，这样直接调用可以优化节约时间其中初始化的方法： lg[i]=lg[i−1]+(1<<lg[i−1]==i)，自己手算一下很清楚的（lg[1~10]为
1 2 2 3 3 3 3 4 4 4，应该很好懂吧）
预处理完了就要倍增求LCA了，我们先把两个点提到同一高度，再统一开始跳。
但我们在跳的时候不能直接跳到它们的LCA，因为这可能会误判，比如4和8，在跳的时候，我们可能会认为1是它们的LCA，但1只是它们的祖先，它们的LCA其实是3。所以我们要跳到它们LCA的下面一层，比如4和8，我们就跳到4和5，然后输出它们的父节点，这样就不会误判了。
然后就是代码了，里面藏着非常详细的注释，相信大家这么强一看就懂 qwq
#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;
struct node
{
ll u,v,nex;
}e[N<<1];
ll head[N],cnt;
void add(ll u,ll v)
{
e[++cnt].v=v;
e[cnt].u=u;//没什么用，还白占空间
e[cnt].nex=head[u];
head[u]=cnt;
}
ll depth[N],fa[N][30],lg[N],s,x,y;
/*dfs函数的作用就是更新该点的所有祖先的fa数组，并通过递归把 该节点的所有的子节点和该节点一样去更新*/
void dfs(ll now,ll fath)//子节点和父节点
{
fa[now][0]=fath;//更新一下fa数组，2^0=1就是父节点
depth[now]=depth[fath]+1;//更新深度
over(i,1,lg[depth[now]]-1)
fa[now][i]=fa[fa[now][i-1]][i-1];
/*更新now的所有 2^i 级的祖先。先找到now的2^(i-1)级祖先，再往上找 该祖先的2^(i-1)级祖先，就是now的2^i祖先，必须一节一节地往上搜*/
for(ll i=head[now];i;i=e[i].nex)//链式前向星遍历
//如果now有子节点的话，就递归往子节点的子节点走（禁止套娃）
if(e[i].v!=fath)
dfs(e[i].v,now);
}
inline ll LCA(ll x,ll y)
{
if(depth[x]<depth[y])//用数学语言就是说不妨设x的深度比y的深度大
swap(x,y);//这样下面只需要写一种代码就好了
while(depth[x]>depth[y])
//让x跳到y的高度（同一高度）
x=fa[x][lg[depth[x]-depth[y]]-1];
//如果跳到一块了那LCA肯定就是y了
if(x==y)
return x;
for(ll k=lg[depth[x]]-1;k>=0;--k)//倒着从大到小地跳
/*因为我们要求跳到x和y的LCA的下一层，所以没有跳到的时候就 让x和y利用dfs里早就用倍增算法处理过的祖先路径快速地一块往上跳*/
if(fa[x][k]!=fa[y][k])
x=fa[x][k],y=fa[y][k];//往上跳
return fa[x][0];//返回x，y的父节点（肯定是相同的嘛）
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&s);
over(i,1,n-1)
{
scanf("%lld%lld",&x,&y);
add(x,y),add(y,x);//无向图一定要记得建双向边
}
over(i,1,n)//预处理一下
lg[i]=lg[i-1]+(1<<lg[i-1]==i);//log2(8)=3//这个手写的lg[]要-1才能用lg[8]=4;
dfs(s,0);//从树根开始，因为用的是链式前向星所以给一个假想根0（其实就是到这儿停）
//dfs一下，预处理各点的深度和祖先
over(i,1,m)
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",LCA(x,y));
}
return 0;
}
三、倍增算法的应用：RMQ 问题（ST表）附模板题
RMQ（区间最值查询）是一个预处理 O（n∗logn）区间极值 O(1)查询任意区间极值的工具
不过显然这个操作可以用线段树来代替，线段树大法好，ST表背不来，我选择线段树，１００多行的线段树看着不香吗（doge）
主要思想就是区间dp出每个点起2的k次方的长度内的极值。运用DP的思想，大区间的极值由小区间得到，同时大区间的答案可以由小区间随意组合得到。比如我们已经预处理1为起点长度为4的答案，和2为起点向后4的答案，我们查询区间1到5的极值就可以比较1-4区间和2-5区间的答案来得到1-5的答案；
预处理的代码如下：
其中f数组的意思是以i为起点 2j 长度的区间的极值是多少
那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值（注意这里的编号是从1开始的）
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]);//取最大值
}
模拟一下：我们要得到 f[1][1]（1往后2格）就可以通过 f[1][0]（1）和 f[2][0]（2）得到， f[1][2]（1往后4格）可以由 f[1][1]（1，2，3）和 f[3][1]（3，4，5）得到。由于我们是小区间得到大区间，所以比如求区间大小为8的时候，我们已经处理了所以4大小的区间了
我们计算出 log2(区间长度)
然后对于左端点和右端点分别进行查询，这样可以保证一定可以覆盖查询的区间
注意从左端点查询的时候是f[l][k]而从右端点开始查的时候左端点是 r−2k+1
因为我们从r开始，需要找到一个左区间x，使得 x+2k−1=r,化简即可得到 x=r−2k+1
查询极值代码如下：
inline ll query(ll l,ll r)
{
ll k=trunc(log2(r-l+1));//其实trunc()可以替换成int()效果一模一样
return max(f[l][k],f[r-(1<<k)+1][k]);//因为已经用区间DP初始化过了，所以直接比较输出即可
}
代码处的k是找2个小一点的区间可以覆盖玩需要查询的区间，比如查找5长度的区间，我们就找2个长度为4的区间完全覆盖查询的区间。为什么能这样，举个例子1 2 4可以任意组合出1-7之内的所有数，正是这个性质才使得这个算法可以存在。
完整代码：
#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;
}
上面的这个代码就是用来解下面的这道模板题的
P3865 【模板】ST表
当然这道水题可以用线段树轻松通过，现在有点太晚了，明天再更
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧
京公网安备 11010502036488号