浅谈倍增

倍增思想

原理：

倍增，即成倍增长。在处理一系列序列数据时，倍增可通过指数级的增长快速覆盖所有数据。

倍增算法采用2倍增长的方式，其核心思想是建立以下数组T a[i][j] ，表示自i向后共 $2^j$ 个数据的某些特性，如最大值等

倍增算法的时间复杂度为 $O (n l o g n)$ ，其中倍增的初始化为 $O (n l o g n)$ ，查询 $O (1)$

实现：

首先，我们需要初始化 $log_2$ 数组，以便查询

log[1] = 0;
for(int i = 2; i <= N; i++)log[i] = log[i/2] + 1;

而后，我们对倍增数组进行初始化，这里倍增数组表示最大值

for(int i = 1; i <= N; i++){cin >> a[i][0];
}
for(int i = 0; i <= N; i++){for(int j = 1; i + (1<<j) - 1 <= N; j++){a[i][j] = max(a[i][j-1],a[i+(1<<(j-1))][j-1]);}
}

最后，我们来实现查询操作

int l,r;
cin >> l >> r;
int k = log[r-l+1];
int ans = max(a[l][k],a[r-(1<<k)+1][k]);

应用

倍增作为一种程序设计的基本思想，广泛应用于各种算法中，其中最常见的用途有三种：快速幂、RMQ、LCA

快速幂

对于要计算的 $a^k$ ，可对 $k$ 进行二进制分解，当 $k$ 最后一位为1时，易知， $ans = a * a^{k-1}$ ，此时我们可以令 $an s * = a$ ，再使得原来的 $a^k$ 变成 $a^{k-1}$ ，其中， $a^{k-1} = (a^2)^{k>>1}$ ，则只需令 $a = a * a$ ，再令$ k = k>>1$

而当 $k$ 的最后一位不为1时，可知， $a^k = (a^2)^{k>>1}$ ，只需令 $a = a * a$ ，再令$ k = k>>1$

int qpow(int a,int k){int ans = 1;while(k){if(k&1)ans*=a;k>>1;a*=a;}
}

RMQ

$RMQ$ 是 $\ Maximum(Mininum)\ Query$ 的缩写，即区间最大/小值的查询问题

最大值查询实现如下：

log[0]=1;
for(int i=1;i<=n;i++)log[i]=log[i/2]+1;
for(int i=1;i<=n;i++)cin>>a[i][0];
for(int i=1;i<=n;i++){for(int j=1;i+(1<<j)-1<=n;j++)a[i][j]=max(a[i-1][j-1],a[i+(1<<(j-1))][j-1]);
}
int k=log[r-l+1];
int ans=max(a[l][k],a[r-(1<<k)+1][k]);

LCA

$L C A$ 是 $Least\ Common\ Ancestors$ 的缩写，即最近公共祖先问题，是树论中的经典问题

如上图， $L C A (5, 9) = 2$

利用倍增思想，我们可以预处理出每个节点的 $2^k$ 级祖先，之后开始操作：

对于两个深度不同的节点，先让深度低的节点向上跳，直到处于相同深度

int lca(int x,int y){if(depth[x]<depth[y]) swap(x,y);while(depth[x]>depth[y]) x=st[x][log[depth[x]-depth[y]]]; if(x==y) return y;for(int k=log[depth[x]];k>=0;k--) if(st[x][k]!=st[y][k]){x=st[x][k];y=st[y][k];}return st[x][0];
}