蓝桥杯软件赛Java研究生组/A组）第二章基础算法-第三节：倍增
一：概述倍增算法：是一种优化算法，通常应用在某些必要高效盘算指数幂的场景。它基于分治的头脑，通过反复求平方来实现快速盘算指数幂的目的。通常应用在最近公共祖先问题、二分查找等等
二：典型标题
（1）标题一（快速幂）
倍增算法最经典的应用就是快速幂，快速幂算法是一种高效盘算大整数幂的方法。如下快速幂盘算 a b a^{b} ab
[*]当 b b b为偶数时
a b = a b 2 ∗ a b 2 = ( a 2 ) b 2 a^{b} = a^{\frac{b}{2}}* a^{\frac{b}{2}}=(a^{2})^{\frac{b}{2}} ab=a2b∗a2b=(a2)2b
[*]**当 b b b为奇数时
a b = a ∗ a b 2 ∗ a b 2 = a ∗ ( a 2 ) b 2 a^{b} = a*a^{\frac{b}{2}}* a^{\frac{b}{2}}=a*(a^{2})^{\frac{b}{2}} ab=a∗a2b∗a2b=a∗(a2)2b
** b 2 \frac{b}{2} 2b向下取整，迭代求解，直到 b b b为0为止
public static long qmi(long a, long b, long p) {
long res = 1;// 初始化结果为 1
while (b > 0) {// 当指数 b 大于 0 时执行循环
if (b & 1 == 1) {// 判断指数 b 的最低位是否为 1
res = res * a % p;// 如果最低位为 1，则将底数 a 的当前幂乘到结果中，并取模 p
}
a = a * a % p;// 底数 a 自乘，相当于计算 a^2, a^4, a^8, ...
b >>= 1;// 将指数 b 右移一位，相当于将指数减半
}
return res;// 返回结果
}
例如盘算 2 13 2^{13} 213
[*] r e s = 2 , a = 2 2 , b = 6 res=2,a=2^{2},b=6 res=2,a=22,b=6
[*] r e s = 2 , a = 2 4 , b = 3 res=2,a=2^{4},b=3 res=2,a=24,b=3
[*] r e s = 2 5 , a = 2 8 , b = 1 res=2^{5},a=2^{8},b=1 res=25,a=28,b=1
[*] r e s = 2 13 , a = 2 16 , b = 0 res=2^{13},a=2^{16},b=0 res=213,a=216,b=0
[*] 倍增一般会和其他算法结合使用
（2）标题二（ST表求区间最值）
https://img-blog.csdnimg.cn/direct/f78bd8b54f5b444895d17617b011efb9.png
思路：见ST表第二节：ST表
int[] arr; // 给定的array
int n = arr.length;
// 预处理log数组，log表示不大于i的最大二进制幂的指数
int[] log = new int;
log = 0;
for(int i = 2; i <= n; i++) {
log = log + 1;
}
// 初始化ST表，st表示从位置i开始，长度为2^J的区间的最值
int[][] st = new int+1];
for(int i = 0; i < n; i++) {
st = arr; // 长度为1的区间的最值就是其本身
}
// 动态规划填表
for(int j = 1; j <= log; j++) {
for(int i = 0; i + (1<<j) <=n; i++) {
st = Math.max(st, st);
}
}
// 查找区间的最值
int k = log;
// 这两个区间为：和
return Math.max(st, st)
（3）标题三（最近公共祖先）
https://img-blog.csdnimg.cn/direct/4d88ad6baa99482099fbebc53879b3b2.png
https://img-blog.csdnimg.cn/direct/4a32fe187e0840868d050914026c7050.png
void dfs(int x, int u) {
dep = dep + 1;// 设置当前节点的深度
father = u; // 直接父节点
// 倍增法处理向上父节点
for(int i = 1; i <= 20; i++) {
father = father];
}
// 递归
for(int y: list) {
if (y != u)
dfs(y, x)
}
}
int lca(int x, int y) {
// 确保x是更深的节点
if (dep < dep) {
swap(x, y);
}
// x向上跳，使x和y在同一深度
for(int i = 20; i >= 0; i--) {
if(dep]>=dep) {
x = father;
}
}
// 如果x和y相等，则找到了lca
if (x == y)
return x;
// 否则，同时开始向上跳，寻找
for(int i = 20; i >= 0; i--) {
if(father != father) {
x = father;
y = father;
}
}
// 返回
return father;
}
int n; // 节点数量
List<Integer>[] list = new List; // 邻接表
for(int i = 0; i <= n; i++) {
list = new ArrayList<>();
}
int[] dep = new int; // 每个节点的深度
int[][] father = new int; // 倍增法，father存储x的2^i父节点
// 深度搜索，初始化dep数组和father数组
dfs(1, 0);
// 求解x和y的lca
lca(x, y)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]