0x00基础算法 -- 0x06 倍增

资料来源：
算法竞赛进阶指南
活动 - AcWing

1、倍增

倍增："成倍增长"，指进行递推时，如果状态空间很大，通常的线性递推无法满足时间和空间复杂度的要求，就可以通过成倍增长的方式，只递推状态空间中在2的整数次幂位置上的值作为代表。当需要其他位置上的值时，通过"任意整数可以表示成若干个2的次幂项的和"这一性质，使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求递推的问题的状态空间关于2的次幂具有可划分性。

倍增思想与二进制划分思想相互结合，可以降低求解很多问题的时间和空间复杂度。例如：“快速幂”
//求 m^ k mod p，时间复杂度 O(logk)。int qmi(int m, int k, int p)
{int result = 1;int t = m;while (k){if (k & 1)result = result * t % p;t = t * t % p;k >>= 1;}return result;
}

1.1 问题一

给定一个长度为N的数列A，进行若干次询问，每次给定一个整数T，求出最大的k，满足 $\sum_{i=1}^{k}A[i]\leq T$ ，你的算法必须时在线的（必须即时回答每一个询问，不能等待收到所有询问后再统一处理），假设 $0\leq T\leq \sum_{i=1}^{k}A[i]$ 。

朴素做法：
从前向后枚举k位，最坏情况位O(N) 。

前缀和+二分：
O(N)处理前缀和，每次询问通过二分比较S[k]与T的大小来确定二分上下界的变化，每次询问花费的时间都是O(log N)。
平均情况下该算法很好，但缺点就是如果每次询问给定的整数T都非常小，造成答案k也非常小，那么该算法可能还不如从前向后枚举更优。

前缀和+倍增算法：

令p=1，k=0，sum=0
比较“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
重复上一步，直到p的值变为0，此时k就是答案

通过若干个长度为2次幂的区间拼成最后的k，时间复杂度级别为答案的对数，能够应对T的各种大小情况。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL; const int N = 1e6 + 10;
LL S[N];//前缀和
int n,m;//n为数组个数，m表示询问次数int main()
{cin >> n >> m;for(int i = 1; i <= n; i++){int a;cin >> a;S[i] = S[i - 1] + a;}while(m--){int t;cin >> t;int p = 1, k = 0, sum = 0; //A数组中k之后的p个数的和while(p) //p为0结束{//注意越界问题if(k + p <= n && sum + S[k+p] - S[k] <= t)sum += S[k+p] - S[k], k = k + p <= n ? k + p : n, p *= 2;else //sum + S[k+p] - S[k] > tp /= 2;}cout << k << endl;}return 0;
}

1.2 题目 -- 天才ACM

109. 天才ACM - AcWing题库

思路：

对于一个集合S，显然应该取S中最大的M个数和最小的M个数，最大和最小的构成一对，次大和次小构成一对...这样求得的"校验值"最大。
求校验值需要进行排序，选取其中最大和最小分别M个值进行计算。
为了让数列A分成的段数最少，每一段都应该在"校验值"不超过T的情况下，尽量包含更多的数，所以从头开始对A进行分段，让每一段尽量长，到达结尾时分成的段数就是答案。
转化问题为：当确定一个左端点L之后，右端点R在满足A[L]~A[R]的"校验值'不超过T的前提下，最大能取到多少。
求某一段的"校验值"需要排序配对，时间复杂度为O(N log N)
利用倍增算法：
令p=1，R=L
求出[L,R+p]区间的"校验值"，若"校验值"<=T，则R += p，p *= 2；否则，p /= 2
重复上一步，直到p的值为0，此时R即为所求。
上述过程至多循环O(log N)次，每次循环需要排序，完成整个题目的求解累计扩展长度为N，所以总体时间复杂度为 $O(N log^{2}N)$ 。可以通过归并排序，只对新增的长度部分排序，然后合并新旧两端，这样总体时间复杂度降低到O(N log N)。
#include <iostream>
#include <algorithm>using namespace std;typedef long long ll;const int N = 500005;int n, m;
int ans;
ll T;
ll w[N], t[N];
ll tmp[N];ll sq(ll 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 ++ )         // 将 w 数组的 [l, r) 区间复制到 t 的 [l, r) 区间中t[i] = w[i];sort(t + mid, t + r);                   // 将 t 的 [mid, r) 排序int i = l, j = mid, k = 0;              // 双指针进行区间合并while (i != mid && j != r)              // 当 i 不到 mid 且 j 不到 r 时，执行循环if (t[i] < t[j])                    // 如果 t[i] 比 t[j] 小，那么将 t[i] 放入 tmp 中tmp[k ++ ] = t[i ++ ]; else                                // 否则将 t[j] 放入 tmp 中tmp[k ++ ] = t[j ++ ];while (i != mid) tmp[k ++ ] = t[i ++ ]; // 处理剩下的元素while (j != r) tmp[k ++ ] = t[j ++ ];ll sum = 0;                             // 计算校验值for (i = 0; i < m && i < k; i ++ , k -- )sum += sq(tmp[i] - tmp[k - 1]);return sum <= T;                        // 返回当前区间 [l, r) 是否合法
}int main()
{int K;scanf("%d", &K);while (K -- ){scanf("%d %d %lld\n", &n, &m, &T);for (int i = 0; i < n; i ++ )scanf("%lld", &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] = tmp[i - start];          // 复制的时候注意下标变换，tmp 是从 0 开始存的，t 是从 start 开始存的}else    len >>= 1;}start = end;ans ++ ;}printf("%d\n", ans);}return 0;
}

2、ST算法

在区间最值问题（RMQ）中，ST算法就是倍增的产物。给定一个长度为N的数列A，ST算法能在O(N log N)时间的预处理后，以O(1)的时间复杂度在线回答"数列A中下标在"l~r"之间的数的最值是多少"。

设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; //利用对数换底公式，将底数e换成2；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\leq 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]的最值。
int ST_query(int l, int r)
{int k = log(r - l + 1) / log(2); //对数换底：log 2 (r - l + 1)return max(f[l][k],f[r - (1 << k) + 1][k]);
}