返回

倍增思想

倍增思想的核心是每次根据已经得到的信息,将考虑的范围扩大一倍,从而加速操作。

在变化规则相同的情况下加速状态转移

这里变化规则相同指的是:

  • 每次的变化规则必须相同
  • 变化规则必须满足结合律(加法,乘法)

我们考虑一下计算2的10次方,怎样算比较快? 最简单我们乘九次即可,但是每次只是乘2是不是太少了,如果乘以4,乘以8,那么计算的次数是不是就会少以些。我们可以先计算2*2,然后4*416*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,依此类推。

img img

在计算这个ST数组时,我们可以使用动态规划重用状态。

$ST[i][j]=min \left{\begin{aligned} ST[i][j-1] \ ST[i+2^j-1][j-1]\end{aligned}\right. $

img 例如: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

Licensed under CC BY-NC-SA 4.0