文章目录1.倍增思想是什么---从一步一步到跳着走1.1 倍增思想的核心本质1.2 倍增思想的数学基础2.快速幂引入倍增思想2.1快速幂数字上倍增2.1.1特殊情况n为2的幂2.1.2一般情况n不为2的幂2.1.3 关键实现代码2.1.4应用 3.ST 表 RMQ3.1.预处理ST表3.2. 处理询问例题板子1.倍增思想是什么—从一步一步到跳着走1.1 倍增思想的核心本质倍增顾名思义就是 “每次增加一倍”。它的核心思想是通过预先计算出问题的 “2k倍” 解在实际求解时将复杂问题分解为若干个 “2k倍” 的子问题从而快速合并得到最终答案。1.2 倍增思想的数学基础倍增思想的数学支撑是二进制分解。任何一个正整数 n都可以唯一分解为若干个不重复的 2 的幂次之和2.快速幂引入倍增思想说到倍增思想 就能想到快速幂了 如果不是接触到倍增思想来详细学一下倍增 还甄不知道快速米这么多用法快速米都能做什么小小的算法也有大大的梦想既然来了就再复习一下快速米吧快速幂的核心思路的是将 b 分解为二进制再通过倍增计算 a 的 2^k 次幂最后将对应位为 1 的项相乘。核心思想二进制拆分任意整数可拆成若干 2k相加预处理提前算出跳2k步的结果查询k从大到小尝试跳跃拼凑答案复杂度预处理O(nlog n)查询O(log n)最简单实例快速幂适用场景线性数组RMQ 区间最值 → ST 表树形结构树上向上跳跃 → LCA、k 级祖先2.1快速幂数字上倍增如何计算an没学到快速幂时 我们肯定都是朴素算法 直接就这样……这一看就是只能说小数据运行 当我们运行到a100000000时 朴素算法需要100000000次 而快速幂算法 只需要27次2.1.1特殊情况n为2的幂有没有快速的方法呢比如说n64;如图演示以此类推可以计算出a64而且仅仅 只需要做6次乘法便可求出a64此刻已经将复杂度优化到了O(logn)这种算法的本质是 倍增原理与其一个一个乘以a不如每次将a的数量翻倍像上面这样叙述的a64是2的倍数幂 倘若不是2的倍数幂呢2.1.2一般情况n不为2的幂eg :计算 a105虽然此刻不是2的倍数幂 但是可以拆分成 a183264在这个情况中 毫无疑问 a8和a32和a64是很容易算出来的 只要用它们相乘就好了 这个关键步骤 是我们如何将n分解成2的幂之和呢关键步骤如下可以从图中看出这几个数的 二进制形式 中只有一个1非常巧的是 我们将105的1拆开刚好可以 得到其他几个数字 通过这个方式我们便可以将105 分解成2的幂之和可以先从中得到伪代码functionB(a,n)r1whilen ≠0ifn mod21rr × a aa × a n⌊n/2⌋// 向下取整等价位运算 n 1returnr让我们通过7105来理解一下这个伪码吧我们先看一下蓝色部分代码当n!0 的时候 就会进入循环体并接在循环结束的时候我们将n除以2并且下取整具体可以观察图中蓝色框内 变化接下来看红色框代码在每次循环结束的时候a就变成a2最后就是黄色框代码了 也就是 这个算法的关键步骤了检查n mod 2是否为1是:就是可分解的2的幂之和总结对于n的二进制我们从低到高不断的遍历它的每一位 如果遍历到的那一位是1那我们就r*a2.1.3关键实现代码functionB(a,n)r1whilen ≠0if(n1)1// 按位与取二进制最低位rr × a aa × a nn1// 右移1位等价于向下取整 n ⌊n/2⌋returnr哦~~原来真理 这样的 终于是彻底搞明白了原理 是还真没这详细的看过快速幂2.1.4应用 1.计算 (anmod m)其中a,m,n都为正整数 在这里的取模运算相当于取余数这种运算方式叫作幂取模运算2.大整数乘法取模的原理倍增 加法取模​ 大整数乘法取模的核心思路是将乘法转化为加法通过倍增累加的方式计算结果本质上和快速幂的逻辑一致快速幂 快速乘快速幂快速算 (anbmod m) 乘法n 次自乘快速乘快速算 (a *b mod m) 加法n 次累加(仅做了解)#includeiostreamusingnamespacestd;typedeflonglongLL;// 快速乘计算 (a * b) mod p避免溢出LLquick_mul(LL a,LL b,LL p){LL res0%p;// 初始化结果为0加法累加的初始值aa%p;// 提前对a取模减少计算量while(b0){// 如果当前b的最低位是1将当前a加到结果中if(b1){res(resa)%p;}// 倍增aa a*2 mod p对应下一个二进制位a(aa)%p;// b右移一位处理下一个二进制位b1;}returnres;}intmain(){LL a,b,p;cinabp;LL resultquick_mul(a,b,p);printf(%lld * %lld mod %lld%lld\n,a,b,p,result);return0;}像洛谷高精度题[P1045 NOIP 2003 普及组] 麦森数 - 洛谷也是借助快速幂实现的//#includebits/stdc.h#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecondconstll N500;constll base10000;usingnamespacestd;ll a[N]{0};ll b[N]{0};ll tmp[N];voidgjd2(ll a1[],ll b[]){memset(tmp,0,sizeof(tmp));for(ll i0;iN;i){if(a1[i]0){continue;}for(ll j0;ijN;j){tmp[ij]a1[i]*b[j];}}for(ll i0;iN-1;i){tmp[i1]tmp[i]/10;tmp[i]%10;}tmp[N-1]%10;memcpy(a1,tmp,sizeof(tmp));}voidksm(ll p){memset(a,0,sizeof(a));memset(b,0,sizeof(b));a[0]1;b[0]2;while(p){if(p1){gjd2(a,b);}p1;if(p){gjd2(b,b);}}a[0]--;}intmain(){IOS ll p;cinp;cout(int)(p*(log10(2)))1endl;ksm(p);ll cnt0;for(ll j499;j0;j--){couta[j];if(j%500){coutendl;}}coutendl;return0;}后两个应用属于矩阵快速幂范畴核心改动把快速幂里的普通乘法替换成矩阵乘法。用来加速线性递推比如斐波那契处理 n 极大1018无法循环模拟的递推题本篇仅做概念了解感兴趣的可以自行查找学习。详情可以去看一下B站up主 五点七边老师的讲解应用 2计算斐波那契数列第 n 项应用 3将线性变换重复 n 次3.ST 表 RMQST表Sparse Table稀疏表主要用来解决RMQ区间最大值/最小值查询问题。主要运用倍增思想可以实现O(nlogn)预处理O(1)查询✅静态含义数组元素不会发生修改❌如果数组存在更新操作ST表不适用需要改用线段树。RMQ问题描述给定长度为n nn的数组m mm次查询。 每次给出区间端点l , r l,rl,r求区间[ l , r ] [l,r][l,r]的最大值最小值逻辑完全同理朴素做法每次查询遍历区间单次查询复杂度O ( n ) O(n)O(n)多次询问大数据下会超时。ST表复杂度 - 预处理O ( n log ⁡ n ) O(n\log n)O(nlogn)- 查询O ( 1 ) O(1)O(1)查询次数很多时优势巨大。凡是符合结合律且可重复贡献的信息查询都可以使用ST表。重复贡献是指对于一个区间将其分成两个重叠的子区间分别计算结果再将两个结果合并而对于最终结果是无影响的。最大值max,最小值min,最大公因数gcd最小公倍数lcm按位与按位或都符合这个条件3.1.预处理ST表倍增法递推用两个等长小区间拼凑一个大区间前半段f [ i ] [ j − 1 ] f[i][j-1]f[i][j−1]起点i ii长度2 j − 1 2^{j-1}2j−1后半段f [ i 2 j − 1 ] [ j − 1 ] f[i2^{j-1}][j-1]f[i2j−1][j−1]起点i 2 j − 1 i2^{j-1}i2j−1长度2 j − 1 2^{j-1}2j−1f [ i ] [ j ] max ⁡ ( f [ i ] [ j − 1 ] , f [ i 2 j − 1 ] [ j − 1 ] ) f[i][j]\max(f[i][j-1], f[i2^{j-1}][j-1])f[i][j]max(f[i][j−1],f[i2j−1][j−1])初始化f[i][0]代表从i出发长度为(2^01)的区间也就是原数组第i个元素。外层循环 jj代表区间长度是2jj20是因为220已经超过106足够处理题目常见数据范围。内层循环 i枚举区间起点。区间右端点 i 2j-1必须n所以条件i(1j)-1n。for(inti1;in;i){cinf[i][0];}for(intj1;j20;j){//枚举区间长度for(inti1;i(1j)-1n;i){//枚举起点f[i][j]max(f[i][j-1],f[i(1(j-1))][j-1]);}}n 6 n6n6区间长度倍增1 , 2 , 4 , 8 , … 1,2,4,8,\dots1,2,4,8,…f [ i , 0 ] f[i,0]f[i,0][ 1 , 1 ] [ 2 , 2 ] [ 3 , 3 ] [ 4 , 4 ] [ 5 , 5 ] [ 6 , 6 ] [1,1]\ [2,2]\ [3,3]\ [4,4]\ [5,5]\ [6,6][1,1][2,2][3,3][4,4][5,5][6,6]f [ i , 1 ] f[i,1]f[i,1][ 1 , 2 ] [ 2 , 3 ] [ 3 , 4 ] [ 4 , 5 ] [ 5 , 6 ] [1,2]\ [2,3]\ [3,4]\ [4,5]\ [5,6][1,2][2,3][3,4][4,5][5,6]f [ i , 2 ] f[i,2]f[i,2][ 1 , 4 ] [ 2 , 5 ] [ 3 , 6 ] [1,4]\ [2,5]\ [3,6][1,4][2,5][3,6]j 3 j3j3i 2 j − 1 1 8 − 1 6 i2^j-118-16i2j−118−16超出数组范围不再处理3.2. 处理询问对查询区间 ([l,r]) 做分割、拼凑区间长度的指数klog2( r- l1)k区间长度集合k0{1}k1{2,3}k2{4,5,6,7}k3{8,9,10,…,15}2 k ≤ r − l 1 2 ⋅ 2 k 2^k \le r-l1 2\cdot 2^k2k≤r−l12⋅2k即区间 [l,r]必可以用两个长度为 2k的区间重叠拼凑。f [ i ] [ j ] max ⁡ ( f [ i ] [ j − 1 ] , f [ i 2 j − 1 ] [ j − 1 ] ) f[i][j]\max(f[i][j-1], f[i2^{j-1}][j-1])f[i][j]max(f[i][j−1],f[i2j−1][j−1])for(inti1,l,r;im;i){cinlr;intklogn[r-l1];coutmax(f[l][k],f[r-(1k)1][k])endl;}思想跳2 k 2^k2k长度 先跳2 k − 1 2^{k-1}2k−1再跳2 k − 1 2^{k-1}2k−1取两段的最大值。例题板子P3865 【模板】ST 表 RMQ 问题 - 洛谷实现代码#includebits/stdc.h#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpairll,ll#defineYEScoutYESendl;#defineNOcoutNOendl;usingnamespacestd;constll N1e510;constll MAXN100005;usingnamespacestd;ll n,m;ll a[N];ll f[N][20];ll logn[N];//初始化对数数组ll l,r;intmain(){IOS cinnm;for(ll i1;in;i){cinf[i][0];}logn[1]0;for(ll i2;in;i){logn[i]logn[i/2]1;}for(ll j1;j20;j){for(ll i1;i(1j)-1n;i){f[i][j]max(f[i][j-1],f[i(1(j-1))][j-1]);}}for(ll i1;im;i){cinlr;ll klogn[r-l1];coutmax(f[l][k],f[r-(1k)1][k])endl;}// coutfixedsetprecision(x) ;return0;}静态数组不支持单点修改只支持重复贡献问题 max/min/gcd不能区间求和。