最近的一次力扣周赛感觉后两道题都偏难，最后一道题可以利用 树上倍增 解决，之前没有接触过个人感觉其思想很类似 动态规划，这里做一个简单记录。

倍增

首先一句话概括倍增的思想核心：

通过预处理一切 规模为 2 的幂次大小 的子问题，然后将真实问题看作成这些子问题的合并。

这种思想通常可以把 $O(n)$ 的时间复杂度映射到其二进制表示的位数上，即 $O(\log n)$。

先放上一道树上倍增的模板题目，通过这个题目可以很好的理解倍增的思想。

1483. 树节点的第 K 个祖先

给你一棵树，树上有 $n$ 个节点，按从 $0$ 到 $n-1$ 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 $0$ 的节点。

树节点的第 $k$ 个祖先节点是从该节点到根节点路径上的第 $k$ 个节点。

实现 TreeAncestor 类：

• TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
• getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 $-1$ 。

提示：

• $1 \le k \le n \le 5 \times 10^4$
• parent[0] == -1 表示编号为 $0$ 的节点是根节点。
• 对于所有的 $0 < i < n$ ，0 <= parent[i] < n 总成立
• $0 \le node < n$
• 至多查询 $5 \times 10^4$ 次

思路

这个题目如果采用暴力的做法，每次查询都需要从当前节点向上遍历 $k$ 次，时间复杂度为 $O(k)$，显然会超时。

这里可以利用倍增的思想，预处理出每个节点的 $2^i$ 祖先，然后每次查询时，只需要将 $k$ 转换成二进制表示，然后从高位向低位遍历，如果当前位为 $1$，则将当前节点向上移动 $2^i$ 步，直到 $k$ 为 $0$。

这么做的道理其实就是把 $k$ 转换成二进制表示，然后将其分解成 $2^i$ 的和，这样就可以将 $O(k)$ 的时间复杂度转换成 $O(\log k)$。距离来看的话，$13$ 的二进制是 $0b1101$，即 $13=12+4+1$，从树的角度来看的话，节点 a 的第 13 个祖先节点就是节点 a 的第 12 个祖先节点的第 4 个祖先节点的第 1 个祖先节点。通过提前预处理出每个节点的 $2^i$ 祖先，就可以在 $O(\log k)$ 的时间复杂度内得到答案。

预处理的长度取决于 k 的范围，即二进制表示最大的位数，针对每个点求出对应的 $log_2(k)$ 个祖先即可。
在预处理的过程中，可以利用动态规划的思想，假设节点 $x$ 的第 $2^i$ 个祖先为 $y$，那么节点 $x$ 的第 $2^{i+1}$ 个祖先就是节点 $y$ 的第 $2^i$ 个祖先，即 $x$ 的第 $2^{i+1}$ 个祖先就是 $y$ 的第 $2^i$ 个祖先的第 $2^i$ 个祖先。状态转移方程如下。

下面给出代码实现。

class TreeAncestor:
    def __init__(self, n: int, parent: List[int]):
        m = n.bit_length() - 1
        pa = [[p] + [-1] * m for p in parent]
        for i in range(m):
            for x in range(n):
                if (p := pa[x][i]) != -1:
                    pa[x][i + 1] = pa[p][i]
        self.pa = pa

    def getKthAncestor(self, node: int, k: int) -> int:
        for i in range(k.bit_length()):
            if (k >> i) & 1:  # k 的二进制从低到高第 i 位是 1
                node = self.pa[node][i]
                if node < 0: break
        return node

    # 另一种写法，不断去掉 k 的最低位的 1
    def getKthAncestor2(self, node: int, k: int) -> int:
        while k and node != -1:  # 也可以写成 ~node
            lb = k & -k
            node = self.pa[node][lb.bit_length() - 1]
            k ^= lb
        return node

参考

• 1483 题解
• 知乎：倍增算法的思想与简单应用