倍增

概述

序列倍增本质上是对于递推的一种优化，通常和二进制拆分（任意一个正整数都可以被拆成 \(2\) 的整数次幂的和）搭配使用。

顾名思义，倍增，就是成倍增长，每次将范围扩大或者减小一倍。

形式化的说，对于一个操作 \(f^n(x)\) 的求值，可以转化为对 \(f^1(x),f^2(x),f^4(x),f^{2^k}(x)\) 的求值。

如果说求 \(f(x)\) 的时间复杂度为 \(O(1)\)，那么求 \(f^n(x)\) 的复杂度可以从原本的 \(O(n)\) 变为 \(O(\log n)\)。

倍增的思想和可以用一个经典的例子，兔子跳来说明。

你现在要从 \(1\) 开始跳到某一个格子 \(t\)，每次只能向前跳 \(2^k\) 步，你不知道这个格子是多少。

然后你每次可以询问交互库一个非负整数 \(k\)，交互库会告诉你你从当前位置跳 \(2^k\) 步是多了还是少了或者到了。

你需要在尽量少的询问次数内到达 \(t\)，保证 \(k \le limit\)。

比如令 \(limit = 8, t = 23\)。

先从大的开始问，\(k = 8\)，\(2^8 = 256 > 23\) 过了，一直到 \(2^5 = 32 > 23\) 都是过了。

然后到了 \(k = 4, 2^4 = 16 < 23\)，发现少了，所以我们能断定 \(t\) 在 \((16,32)\) 之间。

此时跳到 \(16\)，我们继续问，显然 \(k \ge 4\) 的都不会再问了，因为当前就是 \(2^4\)，再多哪怕一个 \(2^4\)，就跳过了。

所以从 \(k = 3\) 开始问，\(16 + 2^3 = 24 > 23\)，过了，再问 \(k = 2\)，\(16 + 2^2 = 20\)，少了，所以跳到 \(20\)。

显然此时 \(k \ge 2\) 的我们都不会问了，因为如果再问一个 \(k = 2\)，那么就会多 \(2^2\)，然后跳到 \(24\)，就跳过了。

所以我们选择问 \(k = 1\)，\(20 + 2^1 = 22 < 23\)，少了，所以跳到 \(22\)，此时最后问 \(k = 0\)，然后就跳到了 \(23\)。

看起来有点麻烦？不过这个过程实际上是 \(O(\log n)\) 的，在数据大起来之后是非常好用的！！

我们总结一下这个过程：

• 可以发现 \(23 = 2^4 + 2^2 + 2^1 + 2^0\)，这是二进制拆分，而出现的指数，恰好都是问交互库了之后我们跳了的 \(k\)，所以倍增有时也可以看作一种二进制拆分。
• 我们每次跳了过后，假设之前问了 \(k\)，那么下一次绝对不会问 \(\ge k\) 的了，这个道理很简单，就是此时再多加一个 \(2^k\)，就跳到了 \(2^{k + 1}\)，已经跳到了上界（开区间）了，肯定不行。（这个点在我们写循环的时候会用到）
• 倍增就是每次看“多了没有？少了没有？”，然后做出对于范围的扩大或者缩小，利用二进制拆分，通过 \(2\) 的整数次幂来构造任意一个非负整数的答案。

写一份简单的代码：

    auto ask_over_or_not = [](int x) -> bool {
        cout << "? " << x << endl;
        int xx; cin >> xx; return xx;
    };

    int nowpos = 1;
    for(int j = 6; j >= 0; --j) { // 根据总结的第二点，我们只需要倒序循环一下就行了。
        bool status = ask_over_or_not(j);
        if(status == 0) nowpos += (1 << j); 
    }

    cout << "! " << nowpos << endl;

当然，你同样可以从小开始跳，本质上没有任何区别，只是我们代码实现的时候枚举指数的顺序从降序变成了升序。

例题

CF1647E，题解。

Warning

推荐求 \(to\) 的时候把 \(j\) 放在外面，因为如果所有的 \(i\) 依次组成的不是一个单调的序列，转移的时候可能出现从 \(to(3) \to to(1)\) 这种。

那么把 \(i\) 放在外面就会有问题，如果 \(i\) 是单调的，那么怎样都行。

这就是倍增，很有意思吧，倍增还有很多比较有意思的应用，

应用

ST 表

区间最值问题可以考虑线段树解决。

不过有一个更好写一点的方法，\(\text{O}(n \log n)\) 预处理，\(\text{O}(1)\) 询问，但是不能带修。

这就是 ST 表，利用倍增的思想考虑：

设 \(f_{i,j}\) 表示从 \(i\) 开始的 \(2^j\) 个数当中的最值。

类似线段树，把两个半区间的信息上传到大区间。

那么 \(f_{i,j}=\max(f_{i,j-1},f_{i+2^{j-1},j-1})\)

询问区间 \([l,r]\) 的最值的时候，找到一个 \(k\) 使得 \(2^k \le r-l+1 \le 2^{k+1}\) （类似我们上面兔子跳说的上界和下界）。

那么 \(ans=\max(f_{l,k},f_{r-2^k+1,k})\)。这两个区间会覆盖，但是没有影响。

const int si = 1e5 + 10;

int st[si][20];
int a[si], Log[si];

void ST_prework() {
    for(int i = 2; i <= n; ++i) {
        Log[i] = Log[i >> 1] + 1;
    }
    for(int i = 1; i <= n; ++i) {
        st[i][0] = a[i];
    }
    for(int j = 1; j <= Log[n]; ++j) {
        for(int i = 1; i <= (n + 1) - (1 << j); ++i) { // 注意循序，此处为了无后效性必须这么写.
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}
inline int query(int l, int r) {
    int k = Log[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

ST 表本质上是对区间可重复贡献问题的求解。

可重复贡献问题是啥？（来源 OI-wiki）

可重复贡献问题 是指对于运算 \(\operatorname{opt}\)，满足 \(x\operatorname{opt} x=x\)，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 \(\max(x,x)=x\)，gcd 有 \(\operatorname{gcd}(x,x)=x\)，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外，\(\operatorname{opt}\) 还必须满足结合律才能使用 ST 表求解。

倍增求 LCA

见 最近公共祖先。

倍增求 Suffix Array

SA 还没学。

---

最后更新: May 9, 2023