倍增

倍增是 LCA 和 ST 表等数据结构常用的思想，它被用来快速访问与一个点距离为 $k$ 的点。只需要维护一个数组 $f{a}_{i,j}$ 表示与点 $i$ 距离为 $2^j$ 的点的下标即可。

示例代码（动态向树插入节点，同时维护 $fa$ 数组）：

// Initialize the root (node 0)
vector<vector<int>> fa = {{}};
vector<int> depth = { 0 };
 
while (q--) {
    read(int, p);  // insert under father node `p`
    depth.emplace_back(depth[p] + 1);
    vector<int> curr = { p };
    for (int i = 1; (1 << i) <= depth[p] + 1; ++i) {
        curr.emplace_back(fa[curr.back()][i - 1]);
    }
    fa.emplace_back(curr);
}

示例代码（访问树上第 $k$ 级祖先）：

auto kth_ancestor = [&] (int v, int k) -> int {
    int ptr = v;
    int b = 0;
    while (k) {
        if (k & 1) {
            ptr = fa[ptr][b];
        }
        k >>= 1;
        b += 1;
    }
    return ptr;
};

二分查找

倍增可以用来在 $O(\log n)$ 时间内查找到特定点距离为多少的点满足某种性质。

例子：CF1516D - Cut

给你一个数组 $a_i$ 和 $q$ 次询问，每次要求求出至少把区间 $[l,r]$ 分成多少段才可以满足每一段中的元素都是互质的。

数据范围 $n,q⩽1e5$。

显然应该贪心地从 $l$ 开始选择尽可能长的连续段。设 $f_{i,j}$ 表示考虑从第 $i$ 个元素开始，向右移动 $2^j$ 个区间之后能达到的最远位置，这样预处理的复杂度是 $O(n\log n)$，查询复杂度是 $O(\log n)$。

Bitwise Binary Search