树上倍增|st表
lc1483
ST表的本质就是二进制拆分，只要满足传递性，可加性即可，和线段树，树状数组，二分查找的底层数学模型是一致的
不得不说，这种记录2^j父节点的想法太巧妙了，第一次见，觉得惊艳。 blow my mind 的感觉，极具美感的算法让人如受洗礼一样，佩服第一次想出这种算法的大佬。
5. 类似的思想在很多算法里都有体现.
6. 树的高度如果是N怎么办，比如退化成链表
7. 代码没变化，复杂度分析没变化。文字确实有个小错误：树的最大的高度是 n 级别的，所以人一个节点到距离为 1, 2, 4, 8, 16, 32 ... 的祖先，最多存储到 logn 这么多祖先的距离，所以状态总数是 nlogn 的。
8. 我一直以为叫ST表
9. st 也用到了 binary lifting 的思想，但 st 不是 binary lifting，st 是指创建一个表快速求查询一个数组的最大值，最小值，和或者其他统计数据。可以参考这里：https://cp-algorithms.com/data_structures/sparse-table.html
class TreeAncestor {
private:
vector<vector<int>> dp;
public:
TreeAncestor(int n, vector<int>& parent) : dp(n) {
for(int i = 0; i < n; i ++)
dp[i].push_back(parent[i]);
for(int j = 1; ; j ++){
bool allneg = true;
for(int i = 0; i < n; i ++){
int t = dp[i][j - 1] != -1 ? dp[dp[i][j - 1]][j - 1] : -1;
dp[i].push_back(t);
if(t != -1) allneg = false;
}
if(allneg) break; // 所有的节点的 2^j 的祖先都是 -1 了，就不用再计算了
}
}
int getKthAncestor(int node, int k) {
if(k == 0 || node== -1) return node;
int pos = ffs(k) - 1; // C++ 语言中 ffs(k) 求解出 k 的最右侧第一个 1 的位置（1-based）
return pos < dp[node].size() ? getKthAncestor(dp[node][pos], k - (1 << pos)) : -1;
}
};