定义

倍增法（binary lifting），顾名思义就是翻倍，可以把线性的处理转换为对数级别的处理，本质是DP。

最常用于解决RMQ（区间最大/小值）问题和求LCA（最近公共祖先）。

LCA

1483. 树节点的第 K 个祖先

$dp[i][j]$：表示距离节点$i$为$2^j$的祖先节点是谁

$dp[i][0]$：就表示距离节点$i$为1的祖先节点，即$i$的父节点

状态转移方程为：$dp[i][j]=dp[dp[i][j-1]][j-1]$

解释：要找到距离节点$i$为$2^j$的祖先，先要找到距离节点$i$为$2^{j-1}$的祖先，然后，再找距离这个祖先为$2^{j-1}$的祖先。这样，两步就可以找到距离节点$i$为$2^j$的祖先。

所以，需要计算距离每一个节点为$1,2,4,8,16,32,\dots$的祖先是谁，直到树的最大高度，这样单个计算时间复杂度为$logn$级别。

预处理时间复杂度为：$O(nlogn)$

public TreeAncestor(int n, int[] parent) {
    dp = new int[n][32];
    // 首先记录每个节点的父节点：2 ^ 0 = 1
    for (int i = 0; i < n; i++) dp[i][0] = parent[i];
    // 动态规划计算距离为 2 ^ j 的祖先
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            // 状态转移
            dp[i][j] = dp[i][j - 1] != -1 ? dp[dp[i][j - 1]][j - 1] : -1;
        }
    }
}Copy

查询时间复杂度为：$O(logk)$

public int getKthAncestor(int node, int k) {
    if (k == 0 || node == -1) return node;
    // 找到k的最高位1所在的位置（0-based）
    int pos = 31 - Integer.numberOfLeadingZeros(k);
    // 递归的查找祖先节点的祖先节点
    return getKthAncestor(dp[node][pos], k - (1 << pos));
}Copy

class TreeAncestor {
    
    int[][] dp;

    public TreeAncestor(int n, int[] parent) {
        dp = new int[n][32];
        // 首先记录每个节点的父节点：2 ^ 0 = 1
        for (int i = 0; i < n; i++) dp[i][0] = parent[i];
        // 动态规划计算距离为 2 ^ j 的祖先
        for (int j = 1; j < 20; j++) {
            for (int i = 0; i < n; i++) {
                // 状态转移
                dp[i][j] = dp[i][j - 1] != -1 ? dp[dp[i][j - 1]][j - 1] : -1;
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
        if (k == 0 || node == -1) return node;
        // 找到k的最高位1所在的位置（0-based）
        int pos = 31 - Integer.numberOfLeadingZeros(k);
        // 递归的查找祖先节点的祖先节点
        return getKthAncestor(dp[node][pos], k - (1 << pos));
    }
}Copy

RMQ

ST表

参考

[1]https://oi-wiki.org/graph/lca/