蓝桥杯软件赛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为止

1. public static long qmi(long a, long b, long p) {
2.     long res = 1;  // 初始化结果为 1
3.     while (b > 0) {  // 当指数 b 大于 0 时执行循环
4.         if (b & 1 == 1) {  // 判断指数 b 的最低位是否为 1
5.             res = res * a % p;  // 如果最低位为 1，则将底数 a 的当前幂乘到结果中，并取模 p
6.         }
7.         a = a * a % p;  // 底数 a 自乘，相当于计算 a^2, a^4, a^8, ...
8.         b >>= 1;  // 将指数 b 右移一位，相当于将指数减半
9.     }
10.     return res;  // 返回结果
11. }

复制代码

例如盘算                                                   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表求区间最值）

   

  思路：见ST表第二节：ST表

1. int[] arr; // 给定的array
2. int n = arr.length;
5. // 预处理log数组，log[i]表示不大于i的最大二进制幂的指数
6. int[] log = new int[n+1];
7. log[1] = 0;
8. for(int i = 2; i <= n; i++) {
9. log[i] = log[i/2] + 1;
10. }
12. // 初始化ST表，st[i][j]表示从位置i开始，长度为2^J的区间的最值
13. int[][] st = new int[n][log[n]+1];
14. for(int i = 0; i < n; i++) {
15. st[i][0] = arr[i]; // 长度为1的区间的最值就是其本身
16. }
18. // 动态规划填表
19. for(int j = 1; j <= log[n]; j++) {
20. for(int i = 0; i + (1<<j) <=n; i++) {
21. st[i][j] = Math.max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
22. }
23. }
25. // 查找区间[L,R]的最值
26. int k = log[R-L+1];
27. // 这两个区间为：[L, L+2^k-1]和[R-2^K+1,R]
29. return Math.max(st[L, k], st[R-(1<<j)+1][k])

复制代码

（3）标题三（最近公共祖先）

1. void dfs(int x, int u) {
2.     dep[x] = dep[u] + 1;// 设置当前节点的深度
3.     father[x][0] = u; // 直接父节点
4.     // 倍增法处理向上父节点
5.     for(int i = 1; i <= 20; i++) {
6.         father[x][i] = father[father[x][i-1]][i-1];
7.     }
9.     // 递归
10.     for(int y: list[x]) {
11.         if (y != u)
12.             dfs(y, x)
13.     }
14. }
16. int lca(int x, int y) {
17.     // 确保x是更深的节点
18.     if (dep[x] < dep[y]) {
19.         swap(x, y);
20.     }
21.     // x向上跳，使x和y在同一深度
22.     for(int i = 20; i >= 0; i--) {
23.         if(dep[father[x][i]]>=dep[y]) {
24.             x = father[x][i];
25.         }
26.     }
27.     // 如果x和y相等，则找到了lca
28.     if (x == y)
29.         return x;
30.     // 否则，同时开始向上跳，寻找
31.     for(int i = 20; i >= 0; i--) {
32.         if(father[x][i] != father[y][i]) {
33.             x = father[x][i];
34.             y = father[y][i];
35.         }
36.     }
37.     // 返回
38.     return father[x][0];
39. }
41. int n; // 节点数量
42. List<Integer>[] list = new List[n+1]; // 邻接表
43. for(int i = 0; i <= n; i++) {
44.     list[i] = new ArrayList<>();
45. }
46. int[] dep = new int[n+1]; // 每个节点的深度
47. int[][] father = new int[n+1][21]; // 倍增法，father[x][i]存储x的2^i父节点
49. // 深度搜索，初始化dep数组和father数组
50. dfs(1, 0);
51. // 求解x和y的lca
52. lca(x, y)

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。