倍增是 LCA 和 ST 表等数据结构常用的思想,它被用来快速访问与一个点距离为 的点。只需要维护一个数组 表示与点 距离为 的点的下标即可。
示例代码(动态向树插入节点,同时维护 数组):
// 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);
}
示例代码(访问树上第 级祖先):
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;
};
二分查找
倍增可以用来在 时间内查找到特定点距离为多少的点满足某种性质。
给你一个数组 和 次询问,每次要求求出至少把区间 分成多少段才可以满足每一段中的元素都是互质的。
数据范围 。
显然应该贪心地从 开始选择尽可能长的连续段。设 表示考虑从第 个元素开始,向右移动 个区间之后能达到的最远位置,这样预处理的复杂度是 ,查询复杂度是 。