倍增模板
作者:
さのpool
,
2024-01-26 22:43:59
,
所有人可见
,
阅读 104
倍增被树剖吊打,用树剖吧
vector<vector<int>> pa;
//获取倍增数组
TreeAncestor(int n, vector<int>& parent) {//n为节点个数
int m = 32-__builtin_clz(n);
pa.resize(n,vector<int>(m,-1));
for(int i = 0;i<n;i++)
pa[i][0] = parent[i];
for(int i = 0;i<m-1;i++)//先循环二进制位
{
for(int x = 0;x<n;x++)
if(int p = pa[x][i];p!=-1)
pa[x][i+1] = pa[p][i];
}
}
//寻找node第k个父节点
任何一个k都可以拆成2^i的和。
int getKthAncestor2(int node, int k) {
for (; k && node != -1; k &= k - 1)
node = pa[node][__builtin_ctz(k)];
return node;
}