倍增思想的核心是每次根据已经得到的信息,将考虑的范围扩大一倍,从而加速操作。
在变化规则相同的情况下加速状态转移
这里变化规则相同指的是:
- 每次的变化规则必须相同
- 变化规则必须满足结合律(加法,乘法)
我们考虑一下计算2的10次方,怎样算比较快?
最简单我们乘九次即可,但是每次只是乘2是不是太少了,如果乘以4,乘以8,那么计算的次数是不是就会少以些。我们可以先计算2*2
,然后4*4
,16*16
,这样我们利用上一次计算的结果,步子越来越大,也就是我们向结果状态转移的速度越来越快,这就是倍增的基本思想。
递归快速幂,先计算a的n/2次方,然后平方;如果n是奇数,那么就先计算a的n-1次方,再乘上a;递归出口是a的0次方为1。
int qpow(int a, int n) {
if (n == 0)
return 1;
else if (n % 2 == 1)
return qpow(a, n - 1) * a;
else
{
int temp = qpow(a, n / 2);
return temp * temp;
}
}
加速区间操作
稀疏表(Sparse Table)主要用来求解RMQ(Range Minimum/Maximum Query)区间最大/最小值查询问题。即给定一个数组,动态查询数组任意区间范围内的最小值。
我们使用倍增的思想预处理数据,定义一个二维数组 f,对于范围内的所有ST[i][j]
表示被查询数组
$[j, j+2^i - 1]$区间的最小值。
我们首先初始化ST[0][j] = a[j]
,然后在长度为2的每个数组子范围中找到最小值,随后长度翻倍为4,依此类推。
在计算这个ST数组时,我们可以使用动态规划重用状态。
$ST[i][j]=min \left{\begin{aligned} ST[i][j-1] \ ST[i+2^j-1][j-1]\end{aligned}\right. $
例如:ST[2][3] = min(ST[1][3], ST[1][5])
查询时我们先计算 $k = \left \lfloor\log_2 (r-l+1) \right \rfloor$ 然后将区间拆分为[r, k-1]和[k, l]
,然后再ST数组上查找即可。
预处理的复杂度为O(nlogn)
,之后查询只需要O(1)
时间。稀疏表的主要缺点是输入数组无法更改。任何更改都将需要新的预计算来恢复数据结构。如果需要在变化的数组中回答最小或最大范围查询,则最好使用段树。
const int MAXN = 105000;
const int MAXLOG = 20;
int n;
int a[MAXN];
int table[MAXLOG][MAXN];
void buildSparseTable() {
for (int i = 0; i <= logs[n]; i++) {
int curLen = 1 << i; // 2^i
for (int j = 0; j + curLen <= n; j++) {
if (curLen == 1) {
table[i][j] = a[j];
} else {
table[i][j] = min(table[i - 1][j], table[i - 1][j + (curLen / 2)]);
}
}
}
}
int getMin(int l, int r) {
int p = logs[r - l + 1];
int pLen = 1 << p; // 2^p
return min(table[p][l], table[p][r - pLen + 1]);
}
此外LCA,和后缀数组都能应用到倍增思想。
为何二倍增
假设为K增,那么相关系数$ \log_2N $就变成了$(k-1)\log_kN$(因为预处理时要向后取用(k-1)
个已知结果才能将范围扩大为原来的k倍),显然这个函数是单调递增的,所以只有在k为2时复杂度最低。
参考文章
http://adilet.org/blog/sparse-table/ https://oi-wiki.org/ds/sparse-table/ https://zhuanlan.zhihu.com/p/95902286 https://wenku.baidu.com/view/33219414a6c30c2259019e54.html