倍增，字面意思就是“成倍增长”。我们在递推时，如果状态空间很大，通常的线性递推无法满足时间和空间复杂度的要求，那么我们就可以通过倍增的方法，只地推空间中2的幂位置上的值作为代表。
当数据普遍很小而空间很大时，二分的效率还不如遍历，而当数据普遍很大时，两者的效率都不如使用倍增的遍历，尽管二分在平均效率上很不错，但在某些情况中倍增会更好用。
例题
Genius ACM（AcWing109）
首先先来看校验值的计算，显然应该取一段范围内最大的M个数和最小的M个数，最大和最小构成一对，次大和次小构成一对……这样求出来的校验值是最大的。而为了让数列A分成的段数最少，每一段都应该在“校验值”不超过T的前提下，尽量包含更多的数。所以我们从头开始分段。
于是，需要解决的问题为：当确定一个左端点L之后，右端点R在满足A[L]~A[R]的“校验值”不超过T的前提下，最多能取到多少。
求长度为N的数列的校验值需要排序，如果使用二分，平均时间复杂度一般是nlogn，当T较小时，二分不如遍历，而且二分第一步就要检验整体一半长度的校验值，而右端点R可能只变化了一点点，浪费很多时间，我们需要一个适配右端点R变化的算法——倍增。
倍增过程可以简单的抽象出来：
1.初始化p=1，R=L
2.求出[L,R+p]这一段的校验值，若校验值<=T,则R+=p，p*=2，否则p/=2.
3.重复上一步，直到p的值变为0，此时R即为所求。
此时我们按照上述思路写一个代码：
tips：以防你不明确m的概念这里简单说一下，我们划分区间时如果大于2*m个数，则只需要找2*m个数来计算校验值，如果小于2*m个数，则全部数都选择，然后尽可能多的对数来计算校验值（如果个数为奇数，则中间有个数不需要计算，个数为偶数的话，则需要排序后计算所有数的校验值）
#include
#include
using namespace std;
long long int m,k,n,t;
long long int s[1000001],a[1000001];
long long int jiaoyan(int l,int r,int d,long long int s[]){
for(int i=l;i<=r;i++){
a[i]=s[i];
}
sort(a+l,a+r+1);
long long int sum=0;
for(int i=l,j=r,e=1;e<=d&&i sum=sum+(a[j]-a[i])*(a[j]-a[i]); } return sum; } int main(){ cin>>k; for(int q=1;q<=k;q++){ cin>>n>>m>>t; for(int i=1;i<=n;i++){ cin>>s[i]; } int l=1,r=1,p=1,ans=1; while(r<=n){ p=1; while(p){ long long int x=jiaoyan(l,r+p,m,s); if(x<=t&&r+p<=n){ r+=p; p*=2; } else p/=2; } if(r ans++; l=r+1; r=l; }else{ cout< r=n+1; } } } return 0; } 然后你就会发现，超时了 该怎么办呢？我们来看时间复杂度，sort是nlogn，倍增也至少也要循环logn次所以是nlog^2n。所以还得对排序下手，可以发现，每次p*2时，前面的部分已经是排序好的了，只需要再排序新插入的部分即可，所以我们可以利用类似归并排序的原理进行排序，此时总体的时间复杂度可以降到nlogn AC代码 #include #include using namespace std; long long int m,k,n,t; long long int s[1000001],a[1000001],b[1000001]; //s为原数组，a为中转数组，b为排好序的数组 long long int jiaoyan(int l,int r,int p){ for(int i=r+1;i<=r+p;i++){ //每次只对新加入的r+1到p进行快速排序， a[i]=s[i]; //因为每次划分新数据时l等于r，不需要担心前面的数据是否有序 } //并且a数组和b数组的l到r都是有序的 sort(a+r+1,a+r+p+1); int begin1=l,begin2=r+1; //与归并排序相似，将排好序的数据存入b数组 for(int i=l;i<=r+p;i++){ if((a[begin1]<=a[begin2]&&begin1<=r)||begin2>r+p)b[i]=a[begin1++]; else b[i]=a[begin2++]; } long long int sum=0; for(int i=l,j=r+p,e=1;e<=m&&i sum=sum+(b[j]-b[i])*(b[j]-b[i]); } return sum; } int main(){ cin>>k; for(int q=1;q<=k;q++){ cin>>n>>m>>t; for(int i=1;i<=n;i++){ cin>>s[i]; } int l=1,r=1,p=1,ans=1; while(r p=1; a[l]=s[l]; while(p){ long long int x=jiaoyan(l,r,p); if(x<=t&&r+p<=n){ //当校验值小于T，r+p还在范围内时，倍增 for(int i=l;i<=r+p;i++){ //此时l到r+p已经被排序好，更新a数组 a[i]=b[i]; } r+=p; p*=2; } else{ p/=2; } } if(r ans++; l=r+1; r=l; } } cout< } return 0; } 谢天谢地找了半天bug终于是ac了。 按照代码的顺序有一些坑仍需要给出提示：（而且都比较基础） 1.sort函数中的两个函数为数组下标，左闭右开，即第二个下标需要+1，不然不会排序最后一个数。 2.归并排序的判断条件，我这里的方式比较简洁，但是如果要这样写的话务必理解判断条件，不然容易出错。 3.a[l]=s[l]这一行需要单独写出来，虽然从l到r+p都是有序的，但是开头的元素是空的需要自己加入，（因为我使用的下标都是从1开始，而且排序的范围都是闭区间）