Binary Lifting

定义

倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。

应用

倍增最常见的应用就是求最近公共祖先 \((Lowest Common Ancestor，LCA)\) 问题和区间最值问题 \((Range Max Question，RMQ)\) 。

LCA

朴素算法

先将两个节点移动到同一层，然后让两个节点一步一步向上跳，直到两点相遇，时间复杂度为树的高度\(O(h)\) 。当我们进行 \(m(m < 1e6)\) 次查询，且节点个数 \(n < 1e3\) 时，朴素算法效率就很低了，复杂度是 \(O(mh)\)。

我们可以做一下简单的优化，将每个节点的每个祖先都记录下来，用数组 \(f[i][j]\) 记录，\(f[i][j]\) 表示第 \(i\) 个节点的第 \(j\) 个祖先，这样每次查询都是 \(O(1)\) ，最后复杂度是 \(O(n^2+m)\) ，空间复杂度是 \(O(n^2)\)。但是当 \(n < 1e5\) 时，这样空间和时间都要超。

倍增

倍增是对朴素算法的优化，从原来的一步一步跳变为每次跳 \(2^j\) 步。比如说我们要向上走 \(11\) 步可以找到最近公共祖先，我们把 \(11\) 写成二进程的形式 \((1011)_2\) ，我们就可以分成三次走，分别走 \(2^3,2^1,2^0\) 步。因为我们每次只会走 \(2\) 幂次步，那么对于每个节点，我们就不必记录其所有祖先，而只记录其 \(2\) 的幂次的祖先，这样就减少了很多不必要的计算。同时我们 \(f[i][j]\) 的含义变为第 \(i\) 个节点的第 \(2^j\) 的祖先

现在就要想办法求出 \(f[i][j]\) 数组。

倍增求 \(LCA\) 实现每次跳 \(2^j\) 步的核心思想就是第 \(i\) 个节点的第 \(2^j\) 的祖先是 \(i\) 节点的第 \(2^{j-1}\) 的祖先的第 \(2^{j-1}\) 的祖先。也就是说将 \(2^j\) 步拆成两个 \(2^{j - 1}\) 步来走。根据这个思路，我们可以写出递推式：

\[ f[i][j]=f[f[i][j-1]][j-1] \]

有了 \(f\) 数组后，就可以求 \(LCA\) 了，对于两个节点 \(x,y\)，我们首先要将两个节点移动到同一深度的位置，这样可以让两个节点一起向上走。移动到同一深度后，我们每次就要走尽可能大的步，但是又要保证两点走后不重合，直到两点不能走为止，此时它们的最近公共祖先就是它们的父节点，即 \(f[x][0]\space or \space f[y][0]\) 。

倍增求 \(LCA\) 模板:

const int MAX = 1e6;
// dep[i]表示节点i的深度
int dep[MAX];
// dp[i][j]表示节点i第2^j的父节点
int dp[MAX][32];
// 邻接表存树
vector<int> s[MAX];

//时间复杂度O(n)
void dfs(int v, int fa) {
    dep[v] = dep[fa] + 1;
    dp[v][0] = fa;
    //dp[i][j]代表第i个节点的第2^i个祖先
    //第i个节点的第2^i个祖先是第i个节点的第2^(i-1)个节点的2^(i-1)个节点
    //递推公式:dp[i][j]=dp[dp[i][j-1]][j-1];
    for (int i = 1; (1 << i) <= dep[v]; ++i)
        dp[v][i] = dp[dp[v][i - 1]][i - 1];
    //遍历子节点
    for (int i = 0; i < s[v].size(); ++i) {
        //不能回到父节点
        if (s[v][i] == fa)continue;
        dfs(s[v][i], v);
    }
}

int lca(int x, int y) {
    //将深度较大的节点换到x上，就不用分类讨论了
    if (dep[x] < dep[y])swap(x, y);
    //计算出两个节点的高度差，将两个节点移到同一层
    int tmp = dep[x] - dep[y];
    //移动的过程和快速幂类似，将高度差按二进制位分解
    for (int i = 0; tmp; ++i) {
        //二进制位为1的，就移动相应步
        if ((tmp & (1 << i))) {
            x = dp[x][i];
            tmp ^= (1 << i);
        }
    }
    if (y == x)return x;
    //两个节点一起移动
    for (int i = 29; i >= 0; --i) {
        //移动要满足移动后两节点不重合，并且在最大步数范围内
        if ((1 << i) <= dep[x] && dp[x][i] != dp[y][i]) {
            x = dp[x][i];
            y = dp[y][i];
        }
    }
    return dp[x][0];
}

RMQ

简介

\(ST\) 表(\(Sparse Table\)，稀疏表)是一种利用倍增思想来处理可重复贡献问题的数据结构。

可重复贡献问题：\(x\space opt\space x=x\)，即对于问题的答案，不会因多计算几次 \(x\) ，而改变，例如 \(MRQ\) 问题、区间 \(gcd\) 问题，他们满足 \(max(x,x)=x\)，\(gcd(x,x)=x\)。另外 \(opt\) 操作要满足结合律，即运算的顺序不会对最终结果产生影响。

【模板题】ST 表

该模板是一个经典的 \(RMQ\) 问题。

暴力做法的话就是每次查询都遍历区间 \([l,r]\) ，来求最大值，这样很显然会超时。

倍增

我们只记录区间 \([i,2^j]\) 的最大值，这样可以用 \(O(n\lg n)\) 的时间复杂度来预处理，每次查询的时间复杂度就是 \(O(\lg n)\) 。我们用表 \(st[i][j]\) 来表示 \([i,i + 2^j - 1]\) 的区间最大值，初始状态是：

\[ st[i][0]=a_i \]

根据定义我们很容易写出倍增的递推公式

\[ st[i][j]=max\{ st[i][j-1],st[i+2^{j-1}][j-1]\} \]

查询的过程就和 \(LCA\) 问题类似，我们利用 \(ST\) 表从 \(l\) 移动到 \(r\) 即可。

倍增求 ST 表模板：

const int MAX = 1e6;
// 元素个数
int n;
int a[MAX];
// st[i][j]表示从i开始2^j的区间内的最大值
int st[MAX][32];
void init() {
    //st表初始化，st[i][0]=a[i]
    for (int i = 1; i <= n; ++i) 
        st[i][0] = a[i];
    //利用递推公式求解 st 表
    for (int j = 1; j < 30; ++j) 
        for (int i = 1; i + (1 << j)-1 <= n; ++i) 
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}

int ask(int l, int r) {
    int rg = r - l + 1, res = -1;
    //利用 st 表每次移动 2^j 步，找到最大值即可
    for (int i = 0; l + (1 << i) - 1 <= r; ++i) 
        if (rg & (1 << i)) 
            res = max(res, st[l][i]),
            rg ^= (1 << i), l += (1 << i);
    return res;
}