倍增，字面意思就是“成倍增长”。这是指我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在2的整数次幂位置上的值作为代表。当需要其他位置的值时，我们通过“任意整数可以表示成若干个2的次幂项的和”这一性质，使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求我们递推的问题的状态空间关于2的次幂具有可划分性。 试想这样一个问题：给定一个长度为N的数列A，然后进行若干次询问，每次给定一个整数T，求出最大的K，满足A[I]+A[2]+…+A[K]<=T。你的算法必须是在线的。 最朴素的做法当然是从前向后枚举K，每次询问花费的时间与答案的大小有关，最坏情况下o(N)； 如果我们能够先花费O(N)的时间预处理A数组的前缀和数组S，就可以二分K的位置，比较S[k]与T的大小来确定二分上下界的变化，每次询问花费的时间都是O(logN)。这个算法在平均情况下表现很好，但是它的缺点是如果每次询问给定的整数T都非常小，造成答案K也非常小，那么该算法可能还不如从前向后枚举更优。 我们可以设计这样一种倍增算法： 1.令p=1,k=0,sum=0； 2.比较"A数组中k之后的p个数的和"与T的关系，也就是说，如果sum+S[k+p]-S[k]<=T，则令sum+=S[k+p]-S[k]，k+=p，p*=2，即累加上这p个数的和，然后把p的跨度增长一倍。如果sum+S[k+p]-S[k]>T，则令p/=2。 3.重复上一步，直到p的值变为0，此时k就是答案。
题目一：天才ACM 给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下: 从集合 S 中取出 M 对数(即 2∗M 个数，不能重复使用集合中的数，如果 S 中的整数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 S 的“校验值”。 现在给定一个长度为 N 的数列 A 以及一个整数 T。 我们要把 A 分成若干段，使得每一段的“校验值”都不超过 T。 求最少需要分成几段。 输入格式 第一行输入整数 K，代表有 K 组测试数据。 对于每组测试数据，第一行包含三个整数 N,M,T 。 第二行包含 N 个整数，表示数列A1,A2…AN。 输出格式 对于每组测试数据，输出其答案，每个答案占一行。 数据范围 1≤K≤12, 1≤N,M≤500000, 0≤T≤1018, 0≤Ai≤220 输入样例： 2 5 1 49 8 2 1 7 9 5 1 64 8 2 1 7 9 输出样例： 2 1
题目思路： 首先，对于一个集合S，显然应该取S中最大M个数和最小的M个数，最大和最小构成一对，次大和次小构成一对，这样求出的“校验值”最大。而为了让数列A分成的段最少，每一段都应该在“校验值”不超过T的前提下，尽量包含更多的数。所以我们从头开始对A进行分段，让每一段尽量长，到达结尾时分成的段数就是答案。 于是，需要解决的问题为：当确定一个左端点L之后，右端点R在满足A[L]到A[R]的“校验值”不超过T的前下，最大能取到多少。假设我们二分取端点R，如果T的值比较小，最终的右端点R可以只扩展了一点儿。浪费了很多时间。所以我们可以使用倍增算法。 1.初始化p=1,R=L； 2.求出[L,R+p]这一段区间的“校验值”，若“校验值”<=T，则R+=p，p*=2，否则p/=2； 3.重复上一步，直到p的值变为0，此时R即为所示。 上面这过程至多循环O(logN)次，每次循环对长为O(R-L)的一段进行排序，完成整个题目的求解累计扩展长度为N，所以总体时间复杂度为O(Nlog＾2N)。实际上我们每次求“校验值”时可以不用快速排序，而是采用类似归并排序的方法，只对新增的长度部分排序，然后合并新旧两段，这样总体时间复杂度可以降低到O(NlogN)。
下述代码中，在处理 [start,end) 的时候，已经将 [start,end)排好序了，所以不需要在处理 [start,end+len)时再排序。 处理 [start,end+len)时，只需要将 [end,end+len) 排序，然后将 [start,end) 与 [end,end+len) 这两段区间进行归并即可。
由于区间 [start,end) 是左闭右开的，直接让 start=end，ans++ 即可
#include<iostream> #include<algorithm> using namespace std; const int N = 500010; long long w[N],t[N],temp[N]; //数组w用来存储输入的数 数组t用来存储排序后的数组 数组temp是归并排序中的额外空间 int ans; long long T; int n,m; long long sq(long long x){ //求平方 return x*x; } bool check(int l,int mid,int r){ // 判断区间 [l, r) 是否合法，并将 t 中的 [l, mid) 区间和 [mid, r) 区间合并到 tmp 中 for(int i=mid;i<r;i++) t[i] = w[i]; // 将 w 数组的 [l, r) 区间复制到 t 的 [l, r) 区间中 sort(t+mid,t+r); // 将 t 的 [mid, r) 排序 int i=l,j=mid,index=0; // 双指针进行区间合并 while(i!=mid&&j!=r){ // 当 i 不到 mid 且 j 不到 r 时，执行循环 if(t[i]<=t[j]) temp[index++] = t[i++]; else temp[index++] = t[j++]; } while(i!=mid) temp[index++] = t[i++]; while(j!=r) temp[index++]= t[j++]; long long sum = 0; for(int i=0;i<m&&i<index;i++,index--){ sum+=sq(temp[index-1]-temp[i]); // 计算校验值 } return sum<=T; // 返回当前区间 [l, r) 是否合法 } int main(){ int k; cin>>k; while(k--){ cin>>n>>m>>T; for(int i=0;i<n;i++){ cin>>w[i]; } ans = 0; int len; int start=0,end=0; while(end<n){ len =1; while(len){ if(end+len<=n&&check(start,end,end+len)){ //如果 w 的 [start, end + len) 区间合法 end+=len;len<<=1; if(end>=n) break; //剪技，如果end>=n 就直接跳出循环 for(int i=start;i<end;i++){ // 在 check 时，已经将 t 数组的 [start, end + len) 这段区间归并在 tmp 中了。现在只需要将 tmp 中的有序数组复制到 t 中即可 t[i] = temp[i-start]; // 复制的时候注意下标变换，tmp 是从 0 开始存的，t 是从 start 开始存的 } } else len>>=1; } start = end; ans++; } cout<<ans<<endl; } return 0; }ST算法： 在RMQ问题（区间最值问题）中，著名的ST算法就是倍增的产物。给定一个长度为N的数列A，ST算法能在O(NlogN)时间的预处理后，以O(1)的时间复杂度在线回答“数列A中下标在l～ｒ之间的数的最大值是多少”这样的区间最值问题。 设F[i,j]表示数列A中下标在子区间[i,i+(2＾j)-1]里的数的最大值，也就是从i开始的2＾j个数的最在值。递推边界显然是F[i,0] = A[i]，即数列A在子区间[i,i]里的最在值。 在递推时，我们把子区间的长度成倍增长，有公式F[i,j] = max{ F[i,j-1] ，F[i+2＾(j-1), j-1]}，即长度为2＾j的子区间的最大值是左右两半长度为2＾(j-1)的子区间的最大值的中较大的一个。
void ST_prework(){ for(int i=1;i<=n;i++) f[i][0] = a[i]; int t = log(n)/log(2)+1; for(int j=1;j<t;j++) for(int i=1;i<=n-(1<<j)+1;i++) f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]); }当询问任意区间[l,r]的最值时，我们先计算出一个k，满足2＾k < r-l+1 <= 2＾(k+1)，也就是使2的k次幂小于区间长度的前提下最大的k。那么“从l开始的2＾k个数”和“以r结尾的2＾k个数”这两段一定覆盖了整个区间[l,r]，这两段的最大值分别是F[l,k]和F[r-2＾k+1,k]，二者中较大的那个就是整个区间[l,r]的最值。因为求的是最大值，所以这两段只要覆盖区间[l,r]即可，即使有重叠也没有关系。
int ST_query(int l,int r){ int k = log(r-l+1)/log(2); return max(f[l][k],f[r-(1<<k)+1][k]); }