C++(倍增法)

分享内容

1. 倍增的思想
2. 快速幂计算
3. ST算法

华为鸿蒙操作系统

HarmonyOS全场景分布式智慧操作系统
鸿蒙操作系统(HarmonyOS)是由中国科技巨头华为公司研发的一款全新的操作系统。它不同
于我们熟知的Windows、macOS或Android等操作系统,鸿蒙OS专为满足万物互联时代的需求而设计,旨在为各种智能设备提供统一、高效的连接与协同能力,让设备之间的互动更加自然流畅。鸿蒙操作系统(HarmonyOS)已经搭载在多种常用设备上,涵盖了智能手机、平板电脑、智能手表、智慧屏、耳机、音箱等多个领域。

什么是倍增?

● 倍增(Binary Lifting),顾名思义就是“成倍增长”,即每次乘2
● 倍增是一种算法技巧
● 如果要从0增长到n,可以用1、2、4、…、2k为“跳板”,快速跳到n
● 这些跳板有k=log2n个
● 倍增法将线性处理(即O(n))转化为对数级(即O(log n))的处理,从而优化时间复杂度

倍增法的应用

“倍增”思想的应用场景

1. 倍增查找:在单调数据组中找某一数值
2. 快速幂计算:就是快速算底数的n次幂
3. ST(Sparse Table)算法:求区间最大(小)值

倍增查找

找有序数据组中某一数值:比如“在一个n个数组成的升序数列中查找第一个>=x的数字”

(1)朴素做法:从第一个数开始,一个一个往后枚举,查找。O(n)
(2)二分查找:每次将数列分割一半判断,并且进一步查找子区间。O(logn)

(3)倍增查找:首先通过倍增的方式快速定位到一个大致的位置,然后通过二分查
找精确地找到第一个大于等于目标值的位置。

· 倍增检查2的整数次幂位置上的值与x的关系,来推算查找范围
· 倍增查找法的时间复杂度是O(logn)

倍增查找代码示例:(有序数组a[n]、左边界L、增长长度p)

intsearch(intx){intL=1,p=1;while(p){//如果还能扩增范围(p>0)就继续if(L+p<=n&&a[L+p]<=x){//a[L+p] 是否满足条件L+=p;//更新左边界p<<=1;//长度成倍增长,相当于p *= 2}else{//长度缩小,相当于p/=2p>>=1;}}returna[L]>=x?L:-1;//第一个>=x的值的位置}时间复杂度O(logn)

● 倍增查找以1、2、4、…、2k为“增长长度”,快速确定查找范围
● 适用于快速定位有序序列中元素的位置
● 时间复杂度O(logn)

● 二分查找法和倍增查找法都利用了二进制的特性来加速算法的执行,但它们在问题解决的方向上相反
● 二分查找是通过缩小搜索范围来定位解,而倍增查找是通过扩大搜索范围来覆盖解空间。

快速幂

快速幂代码示例:计算aⁿ

intfastPow(inta,intn){longlongbase=a;//二进制某位的权重,初始是最低为权重为longlongans=1;while(n){if(n&1)//如果n的最后一位是1,表示这个地方需要乘ans*=base;//累乘和累加使值快速增长,数值会溢出base*=base;//推算乘积,a^2 ->a^4 ->a^8->a^16n>>=1;// n右移一位,把刚处理过的n的最后一位去掉}returnans;}时间复杂度O(logn)

快速幂(取模)

快速幂题目一般会提供模数,并要求进行取模运算

取模运算的分配律规则,包括:

(A+B)mod b=(A mod b+B mod b)modb(A-B)mod b=(A mod b-B mod b)modb(A x B)mod b=((A mod b)x(B mod b))mod b

分块模运算防止溢出

在可能导致溢出的计算处加入取模运算

ans= base----------------ans = (ansbase) % p(如果题目不要求取模,则不需要这一步)

快速幂运算并取模:aⁿ mod p

intfastPow(inta,intn,intp){longlongbase=a%p;longlongans=1;while(n){if(n&1)// 如果n的最后一位是1,表示这个地方需要乘ans=(ans*base)%p;base=(base*base)%p;//推算乘积,a^2 ->a^4->a^8->a^16 ..n>>=1;// n右移一位,把刚处理过的n的最后一位去掉}returnans;}

Pow函数和快速霧

●快速幂算法利用了二进制的性质,将指数n表示为二进制形式,然后通过log2n次乘法来计算aⁿ

●C++自带的pow函数就是求次幂的:计算aⁿ,写法是pow(a,n)
●pow函数是基于浮点运算的,返回值也是浮点型,转整型时可能有精度丢失的问题
● 所以计算整数幂时,推荐使用快速幂运算法避免精度丢失的问题
● 我们也需要理解快速幂的原理,因为可能会遇到变种题

快速模霧

给你三个整数a、b、p,求a^b mod p。
【输入格式】
输入只有一行三个整数,分别代表a、b、p。
【输出格式】
输出一行一个字符串a^b mod p=s,其中a,b,p分别为题目给定的值,s为运算结果。
对于100%的数据,保证0≤a,b<2∧13,a+b>0,2≤p<2^31。
【输入样例1】2 109
【输出样例1】2^10 mod 9=7
【输入样例2】2 10 100
【输出样例2】2^10 mod 100=24
由于a、b、p数据的取值范围太大,规做法会超时,只能用快速幂。

定义函数快速计算a^n并对mod取模

使用long long 可以确保在取模之前,乘法操作不会导致溢出,从而保证模运算的正确性

long long fastPower(long long a, long long n, long long mod)

具体步骤如下:

1. 初始化result=1,基数base=a(两者也为long long类型)
2. 从右到左遍历指数n的二进制表示,对于每个二进制位:
   ①如果当前位是1,将result=result*base,并对mod取模。
   ②将base=base2,并对mod取模。
3. 最终得到的result 就是a^n%mod。

【提示】用位与&和右移>>实现二进制位的遍历

函数代码示例:longlongfastPower(longlonga,longlongn,longlongmod){longlongresult=1;longlongbase=a%mod;while(n>0){if(n&1)// 如果当前最低位为1result=(result*base)%mod;base=(base*base)%mod;n>>=1;// 右移一位}returnresult;}时间复杂度为O(logn)

完整代码

#include<iostream>usingnamespacestd;// 快速计算a^n,并对mod取模// 时间复杂度O(logn)longlongfastPower(longlonga,longlongn,longlongmod){longlongresult=1;longlongbase=a%mod;while(n>0){if(n&1)//如果当前最低位为1result=(result*base)%mod;base=(base*base)%mod;n>>=1;// 右移一位}returnresult;}intmain(){longlonga,b,p;cin>>a>>b>>p;printf("%lld^%11d mod %11d=%11d",a,b,p,fastPower(a,b,p));return0;}

总时间复杂度O(logn)

注意对输出样式的要求。

ST算法

● ST(Sparse Table)（散列表）算法:求解RMQ（Range Minimum/Maximum Query）问题的优秀算法
●RMQ问题,即区间最值问题:给定长度为n的静态数列,做m次询问,每次给
定L,R,查询区间[L,R]内的最值。

(1)暴力法:
1次查询:搜区间[L,R],逐一比较区间内的每个数找到最值,复杂度为O(n)
m次查询:总复杂度O(mn),效率很低
(2)ST(散列表)法

ST算法的原理

核心思想:一个大区间若能被两个小区间覆盖,那么大区间的最值等于两个小区间的最值。

· 大区间被两个小区间覆盖:大区间的任意一个元素必须属于起码一个小区间,也可以同时属于两个小区间(两个小区间的重合部分)
· 大区间的最小值等于两个小区间的最小值中的小者,min{1,2}=1
· 如果有够多的小区间,就可以满足各种区间范围的查询

ST算法的步骤

ST算法求最值的步骤
①预处理:把整个数列分为很多小区间,并提前计算出每个小区间的最值

② 多次查询:对任意一个区间[L,R]的查询,可以通过找到覆盖它的两个小区间,用这两个小区间的最值算出答案

ST算法-预处理

ST算法-查询

ST算法的特点

● 可以在O(nlogn)的时间内完成预处理,并在O(1)的时间内回答每个查询
● 需要存储不同小区间内的最值,因此其空间复杂度一般也是O(nlogn)

ST算法应用场合
静态数组。如果数据发生了变化,所有ST表要重新计算。
极大的查询次数。每次查询的复杂度只需要O(1)

区间最值

给定一个长度为N的数列,和M次询问,求出每一次询问的区间内数字的最大值。
【输入格式】
第一行包含两个整数N、M,分别表示数列的长度和询问的个数。
第二行包含N个整数(记为ai),依次表示数列的第i项。
接下来M行,每行包含两个整数li,ri,表示查询的区间为[li,ri]。
【输出格式】
输出包含M行,每行一个整数,依次表示每一次询问的结果。
对于100%的数据,满足1≤N≤10∧5,1≤M≤2×10∧6, ai∈[0,10^9], 1≤li≤ri≤N

ST算法-预处理

ST算法-查询

完整代码

#include<iostream>#include<cmath>usingnamespacestd;#defineN100001inta[N];intst[N][20];// st[i][j]表示数列在[i,i+2^j-1]里的最大值// 初始状态是 st[i][0]=a[i]// 递推公式 st[i][j]=max(st[i][j-1],st[i+(1 << (j-1))][j-1])intn,m,l,r;// 预处理ST表voidST_create(){for(inti=1;i<=n;i++)//第0组st[i][0]=a[i];for(intj=1;(1<<j)<=n;j++){//第1~logn组/*等同于: int K = (int)log2(n) ; for (int j = 1; j <= K; j++)*/for(inti=1;i<=n-(1<<j)+1;i++){// 1~ n-2^j+1st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}}//查询区间[L,R]的最大值intSTquery(intL,intR){intk=log2(R-L+1);returnmax(st[L][k],st[R-(1<<k)+1][k]);}intmain(){cin>>n>>m;for(inti=1;i<=n;i++)scanf("%d",&a[i]);ST_create();while(m--){cin>>1>>r;cout<<ST_query(1,r)<<endl;}return0;}

总时间复杂度
O(nlogn)+O(m) = O(nlogn)

试着加入输出语句,把ST表打印出来看看!

本次课程的知识点

1. 倍增法的原理

2. 倍增法的三种典型应用场景:

① 倍增查找

②快速幂计算

③ST算法求区间最值
1、对二维数组 int arr[3][16];arr[1]占内存为(D)字节?

A、4

B、16

C、48

D、64

【提示】对于二维数组 int arr[3][16],它是一个3行16列的数组,每个元素都是int类型。
通常,int类型占用4个字节(32位)。arr[1]表示数组的第二行,它包含16个int类型的
元素。因此,arr[1]占用的内存字节数为16*4=64字节。
2、下面C++代码执行后输出是©?

intmain(){cout<<(3|16)<<endl;return0;}

A, 3

B. 16

C, 19

D. 48

【提示】“I’是位运算符,进行位或计算。0011|10000=10011=1910

倍增查找

请在一个有序递增数组中(不存在相同元素),用倍增法,找出第一个>=x的值的位置,如
果x在数组中不存在,请输出-1!
【输入】
第一行,一个整数n,代表数组元素个数(n <= 100)
第二行,n个整数,代表数组的n个递增元素(1 <= 数组元素值 <= 10^8)
第三行,一个整数x,代表要查找的数(0 <= x <= 10^8)
【输出】
x在数组中的位置,位置从1开始编号;没找到,输出-1。

#include<iostream>usingnamespacestd;inta[110];intn;//在数组a[1~n]中倍增查找x的位置// 如果找到x,则返回x在数组a中的下标,否则返回-1intsearch(intx){intL=1,p=1;while(p){//如果还能扩增范围(1)就继续if(L+p<=n&&a[L+p]<=x){L+=p;//增加已知范围p<<=1;//成倍增长,相当于p *= 2}else{p>=1;//缩小范围}}returna[L]>=x?L:-1;}intmain(){intx;// 要查找的值cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}cin>>x;cout<<search(x);return0;}