倍增¶
应用：进行递推时，若状态空间过大，则只推出\(2^k\)位置上的值。当需要其它位置上的值时，利用任意整数可以表示为若干个2的次幂项之和的性质从\(2^k\)位置的值中拼出结果。
例1 给定长度为\(N\)的数列\(a\)，然后在线询问若干次，每次给定一个整数\(T\)，求\(k_{max}\space s.t.\sum\limits_{i=1}^ka_i\leqslant T\).\((0\leqslant T\leqslant\sum\limits_{i=1}^Na_i)\)
思路1：二分查找
对\(\{a_n\}\)进行预处理求出前缀和\(S_n\)，然后二分\(\{S_n\}\)找\(k_{max}\space s.t.S_k\leqslant T\).
由于每次查找平均花费\(O(logN)\)，当\(k\)较小时不如直接遍历。
思路2：倍增+二进制划分
先考虑这样一个问题：如何将一个未知的数\(n\)进行二进制分解？
若我们从低位开始分解，由于我们并不知道\(n\)的值，无法确认当前位上的是0还是1，所以无法进行分解。
当我们从高位开始分解时，若找到\(k_0\space s.t.2^{k_0}>n\)，我们能确定\(\forall k\geqslant k_0,2^k\geqslant2^{k_0}>n\)，即\(n\)的第\(k_0\)位及以上都不可能是1。
从\(k_0\)向下寻找到第一个\(k_1\space s.t.2^{k_1}\leqslant n\)，我们能确定\(n\)的第\(k_1\)位一定是1。否则若\(k_1\)位不是1，那么\(n\leqslant \sum\limits_{k=0}^{k_1-1}2^k=2^{k_1}-1<2^{k_1}\leqslant n\Rightarrow n<n\)，矛盾！所以\(n\)的第\(k_1\)位是1。
从\(n\)中扣除\(2^{k_1}\)后，问题转化为分解\(n-2^{k_1}\)，重复上述步骤即可将\(n\)完全分解。
所以我们要构造一种能使得从高位进行二进制分解的情形。
为此，我们分两个阶段来进行：
阶段1：倍增
依次考虑\(S_1,S_{1+2^1},S_{1+2^1+2^2},\dots\)，直到出现\(S_{\sum_{i=0}^{k_0}2^i}>T\)停止。此时\(k_{max}<\sum\limits_{i=0}^{k_0}2^i\).令\(k=\sum\limits_{i=0}^{k_0-1}2^i\)，则\(k_{max}-k<2^{k_0}\)，可对\(k_{max}-k\)进行二进制划分。
阶段2：二进制划分
依次考虑\(S_{k+2^{k_0-1}},S_{k+2^{k_0-2}},\dots\)，若\(S_{k+2^{k_1}}\leqslant T\)，则相当于找到了\(k_{max}-k\)的二进制最高位\(k_1\)；继续考虑\(S_{k+2^{k_1}+2^{k_1-1}},S_{k+2^{k_1}+2^{k_1-2}}\dots\)，相当于对\(k_{max}-k-2^{k_1}\)继续进行二进制分解。当\(k_m<0\)时，分解完毕，\(k_{max}=k+\sum\limits_{i=1}^{m-1}2^{k_i}\).
实现：
int p = 1, k = 0, sum = 0;
while (p) {
if (k + p <= N && sum + S[k + p] - S[k] <= T)
sum += S[k + p] - S[k], k += p, p <<= 1; // 1.
else p >>= 1;
}
细节：
1.数组\(a\)下标从1开始。\(S_r-S_l\)所求的是\((l,r]\)上的部分和，倍增过程即\((0,1]+(1,1+2]+(1+2,1+2+4]+\dots=(0,1+2+4+\dots+2^{k_0-1}]=[1,k]\)
由于二进制划分过程中下标仍递增，所以两个阶段可以合并，如图：
倍增与二分查找的比较：
倍增：利于已遍历状态空间的扩增（求增）
二分查找：利于有序状态空间的搜索（求全）
例2 Genius ACM
思路：倍增+二路归并
先解决校验值。当\(M=1\)时，显然\(S_{校验}=(\max S-\min S)^2\).
当\(M=2\)时，参考\(M=1\)的情形将\(S\)进行排序。若所取的数\(S_i\)不为\(S_1,S_2,S_{n-1},S_n\)，那么\(|S_i-S_j|<\max(|S_1-S_j|,|S_2-S_j|,|S_{n-1}-S_j|,|S_n-S_j|)\).因此，我们只需考虑\(S_1,S_2,S_{n-1},S_n\)的组合方式即可。
又\([(S_n-S_1)^2+(S_{n-1}-S_2)^2]-[(S_n-S_2)^2+(S_{n-1}-S_1)^2]=2S_1S_{n-1}+2S_2S_n\)\(-2S_1S_n-2S_2S_{n-1}=2S_2(S_n-S_{n-1})-2S_1(S_n-S_{n-1})=2(S_2-S_1)(S_n-S_{n-1})>0\)，所以\(S_1\)与\(S_n\)组合，\(S_2\)与\(S_{n-1}\)组合。
类似的，当\(M>2\)时我们可以进行类似的组合。
所以从头尾选数进行组合即可求得\(S_{校验}\)。
此处的\(S_{校验}\)类似于上题的前缀和，我们可以采用相同的框架进行求解。
需要注意的一个细节是，求\(S_{校验}\)时，我们需要对目标区间\([l,r]\)进行排序。这里会出现两个问题，一是每次进行排序时需花费\(O(nlogn)\)，加上\(O(logn)\)的倍增次数，算法复杂度为\(O(nlog^2n)\)；二是排序会对原数组造成影响，例如判断\([l,r+2k]\)时对\([l,r+2k]\)进行了排序，若此时不符合条件，区间回退至\([l,r+k]\)，但\([l,r+k]\)中混入\([r+k+1,r+2k]\)的元素导致错误。
第一个问题可以采用二路归并实现：当排序区间从\([l,r]\rightarrow[l,r+p]\)时，可以对\([r+1,r+p]\)进行排序，再将\([l,r],[r+1,r+p]\)进行归并，即可得到\([l,r+p]\)的有序区间。每次有效排序（即产生扩增时的排序）长度\(n_i\)满足\(\sum n_i=n\)，故\(\sum n_ilogn_i<\sum n_ilogn=nlogn\)，复杂度降为\(O(nlogn)\).
解决第二个问题需要三个数组：\(a[],b[],temp[]\)，其中\(a[]\)存储原数据，\(temp[]\)为归并辅助数组，\(b[]\)为部分有序数组。三个数组工作如下：
扩增过程：\([l,r+p]\)符合条件，区间即从\([l,r]\)扩增到\([l,r+p]\).由于右端点只增不减，所以可以确定将有序的\([l,r+p]\)存入\(b[]\)不会导致后面元素的混入。
需要注意的是，我们不能仅将有序的\([r+1,r+p]\)直接放入\(b[]\)中，因为对\([l,r+p]\)整体排序后，\([l,r]\)部分也发生了改变，需将\([l,r+p]\)全部拷入。
试探过程：我们期望得到\([l,r+p_0]\)的有序序列，而这次扩增是在\([l,r]\)基础上的，所以\(b[]\)中\([l,r]\)部分是有序的。为了实现二路归并的效果，我们应该把\(a[r+1,r+p_0]\)拷入\(b[]\)中，并对\(b[]\)中该部分进行排序，再由归并后进入\(temp[]\)中。
此时\(temp[]\)中持有\([l,r+p_0]\)的有序序列，所以可以直接在\(temp[]\)中求取\(S_{校验}\).而传统的归并排序要求我们将\(temp[]\)拷入\(b[]\)中，但让未经确认的\([l,r+p_0]\)进入\(b[]\)会使得\([r+1,r+p_0]\)的元素混入\([l,r]\)中，从而产生未确定元素对已确定元素的破坏。
回到扩增过程，有序的\([l,r+p]\)的来源即是\(temp[]\)，在试探过程中已经排好序放入\(temp[]\)中，可以在试探成功后直接取用。
实现：
int a[N], b[N], temp[N], m, n;
long long t;
bool check(int l, int mid, int r) {
if (r >= n)
return 0;
for (int i = mid + 1; i <= r; i++)
b[i] = a[i];
sort(b + mid + 1, b + r + 1); // STL区间左闭右开
int i = l, j = mid + 1; // 二路归并
for (int pos = l; pos <= r; pos++)
if (j > r || (i <= mid && b[i] < b[j]))
temp[pos] = b[i++];
else
temp[pos] = b[j++];
long long res = 0;
if (r - l + 1 <= 2 * m) // 数不够选
for (int i = 0; 2 * i < r - l; i++) // l + i < r - i
res += pow((temp[l + i] - temp[r - i]), 2);
else
for (int i = 0; i < m; i++)
res += pow((temp[l + i] - temp[r - i]), 2);
return res <= t;
}
int main() {
int k, p, ans, l, r;
cin >> k;
while (k--) {
cin >> n >> m >> t;
for (int i = 0; i < n; i++)
cin >> a[i];
ans = 0, l = 0, r = 0;
while (r < n) {
p = 1, b[r] = a[r]; // 1.
while (p) {
if (check(l, r, r + p)) {
r += p, p <<= 1;
for (int i = l; i <= r; i++)
b[i] = temp[i];
} else
p >>= 1;
}
ans++, l = ++r; // 1.
}
cout << ans << endl;
}
return 0;
}
细节：
1.当产生新的分段时，\([l_1,r_1]\)划分结束，\(l_2=r_1+1,r_2=l_2\)开始新的划分，但在试探过程中，我么假定了\([l,r]\)是有序序列，而有序序列应被拷入\(b[]\)中，所以每一次开始新的分段时，需将\(a[l](a[r])\)拷入\(b[]\)中以保证正确性。
ST算法¶
应用：求解RMQ问题
RMQ问题：给定长度为\(N\)的数列\(a\)，在线回答数组\(a\)中下标在\(l\sim r\)之间的数的最大值为多少
思路：倍增
根据倍增思想，我们希望引入成倍增长的量，易见区间长度是很好的选择。为了描述各个区间，规定长度后还需规定起点，所以我们将起点和长度作为状态描述的参量。
定义状态\(F[i][j]\triangleq \max\limits_{i\leqslant k\leqslant i+2^j-1}a_k\)，即从\(a_i\)开始区间长度为\(2^j\)（\(i+2^j-1-i+1=2^j\)）的区间的最大值。边界为\(F[i][0]=a_i\).
接着考虑状态转移，考虑到最大值的性质：两个区间合起来的最大值等于两个区间各自的最大值的最大值，所以\(F[i][j]=\max\{F[i][j-1],F[i+2^{j-1}][j-1]\}\)（前半个区间到\(i+2^{j-1}-1\)，后半个区间从\(i+2^{j-1}\)开始）
状态空间大小为\(n*logn\)，故预处理\(F[n][logn]\)的时间复杂度为\(O(nlogn)\).
接着考虑查询过程。由于两个区间合起来的最大值等于两个区间各自的最大值的最大值，所以我们可以将待查区间分为两段（重合不影响合区间，只需要求两段区间的合将待查询区间覆盖即可）。结合我们定义的状态，我们可以考虑使用\(F[l][k]\)和\(F[r-2^k+1][k]\)进行查询，如图：
故要求\(\left\{\begin{array}{ll}2^k\leqslant l-r+1, \\2\cdot2^k\geqslant l-r+1\end{array}\right.\)取\(k=\lfloor log_2(l-r+1)\rfloor\)即可(\(p-1\leqslant p-1<\lfloor p\rfloor\leqslant p\))。
实现：
for (int i = 1; i <= n; i++) f[i][0] = a[i];
int t = log[n]; // 1.
for (int j = 1; j <= t; j++)
for (int i = 1; i <= n - (1 << j) + 1; i++) // 2.
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
void query(int l, int r) {
int k = log[r - l + 1];
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
细节：
1.此处使用预处理的\(log\)表计算\(log_2n\)，预处理\(log\)表实现如下：
即\(\forall n\in[2^{i},2^{i+1}),n\in\N^*,\lfloor log_2n\rfloor=i\).
或者可以使用\(cmath\)库的\(log\)函数，该函数以10为底。由换底公式知，\(log_2n=\dfrac{lgn}{lg2}\)，故\(log[n]=log(n)/log(2)\)
2.状转方程右边的\(j-1\)小于左边的\(j\)，所以需要按照\(j\)递增的顺序进行枚举，故将\(j\)放在外层循环；递推\(i\)时需判断边界：\(F[i][j]\)本身含义是\([i,i+2^j-1]\)，故\(i+2^j-1\leqslant n\Leftrightarrow i\leqslant n-2^j+1\)